Dijkstra Algorithm is used to find shortest path.
this algorithm is well-known because many applications which programmed by this algorithm we are using in practice.
Subway Map, GeoGraphic Infomation System and so on.
Before posting this algorithm, I had to study many things to understand for this one.
# List #
3. Prim algorithm,
4. Union Find algorithm,
5. Kruskal algorithm,
6. Topology algorithm,
After writing those code in Java, I was able to totally understand Dijkstra Algorithm, usages where to use and how to customizing,
1 function Dijkstra(Graph, source): 2 3 dist[source] ← 0 // Distance from source to source 4 prev[source] ← undefined // Previous node in optimal path initialization 5 6 for each vertex v in Graph: // Initialization 7 if v ≠ source // Where v has not yet been removed from Q (unvisited nodes) 8 dist[v] ← infinity // Unknown distance function from source to v 9 prev[v] ← undefined // Previous node in optimal path from source 10 end if 11 add v to Q // All nodes initially in Q (unvisited nodes) 12 end for 13 14 while Q is not empty: 15 u ← vertex in Q with min dist[u] // Source node in first case 16 remove u from Q 17 18 for each neighbor v of u: // where v has not yet been removed from Q. 19 alt ← dist[u] + length(u, v) 20 if alt < dist[v]: // A shorter path to v has been found 21 dist[v] ← alt 22 prev[v] ← u 23 end if 24 end for 25 end while 26 27 return dist, prev 28 29 end function
this is graph start from node 1
check length (weight)
visit node 2 (minimu length from visited to none visited)
and check neighbors length
this is what shortest path
and I will show you my java code and this has two testcase
firstcase is from wekipedia
secondcase is from geeksforgeeks
if you like....
if you have question...
if you found something is strange...