Java

Assignment # 4 Shortest Path Algorithm Implementation of Dijkstra's Shortest path algorithm Djikstra's algorithm (named after its discoverer, E.W. Dijkstra) solves the problem of finding the shortest patlh from a point in a graph (the source) to a destination. One can find the shortest paths from a given source to all points in a graph at the same time. Hence this problem is sometimes called the single-source shortest path problem. Dijkstra's algorithm finds the shortest path from x to y in order of increasing distance from x. That is, it chooses the first minimum edge, stores this value and adds the next minimum value from the next edge it selects. It starts out at one vertex and branches out by selecting certain edges that lead to new vertices. It is similar to the minimum spanning tree algorithm, in that it is "greedy", always choosing the closest edge in hope of an optimal solution. Pseudo Code for Dijkstra's Algorithm Void dijkstra(Vertex s) Vertex v.w: s.dist = 0: for() v = smallest unknown distance vertex: if(v--null) ?known = true: for each w adjacent to v break if (!w.known) if (v.dist + cvw