Dijkstra algorithm is an algorithm for finding the shortes paths between nodes in a graph.
A very common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.
It can also be used for finding the shortes paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.
Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.
function Dijkstra(graph, source): create vertex set Q for each vertex v in graph: add v to Q // Add the node to the set Q dist[v] = INFINITY // Unknown distance from source to v prev[v] = UNDEFINED // Previous node in optimal path from source dist[source] = 0 // Distance from source to source while Q is not empty: u = vertex in Q with min dist[u] remove u from Q for each neighbor v of u alt = dist + length(u, v) if alt < dist[v] dist[v] = alt prev[v] = u return dist, prev // return distances and path links
The shortest path algorithm is widely used in network routing protocols, most notably IS-IS and OSPF.
Both the protocols are link-state routing protocol used for routing data within an autonomous system (interior gateway protocols), operating by reliably flooding link state information throughout a network of routers.
Proudly self-hosted on a cheap Raspberry Pi