Coders Packet

Shortest Path Problem using Java

By Soham Ghosh

The project finds the shortest path distance from the source vertex to all the vertices of a graph using Java.

The algorithm used in this project is Dijkstra's algorithm, which provides an optimal solution to this problem. The graph is represented using an adjacency matrix and two arrays are maintained for each vertex of the graph: dist[] which stores the distance value and processed[] which stores whether the vertex is processed or not.

The project uses two user-defined methods: minVertex(), which finds the vertex with minimum distance value and findShortestPath(), which finds the shortest path distance from the source vertex to all the vertices of the graph. In findShortestPath(), until all the vertices are covered, at every step, an unprocessed vertex u using minVertex() is found and the distance value of all the adjacent vertices of u are updated to the minimum possible value.

In main(), an example graph G[][] with vertices V is used to find the shortest path distance from vertex 0, which is taken as the source vertex.

The drawback of Dijkstra's algorithm is that for a graph with negative edge weights, the algorithm may or may not work.

 

Download project

Reviews Report

Submitted by Soham Ghosh (sohamghosh1509)

Download packets of source code on Coders Packet