Dijkstra's Algorithm: Difference between revisions

From Rice Wiki
No edit summary
No edit summary
Line 5: Line 5:
Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.''
Dijkstra's algorithm centers around this property: ''of all the edges leaving the source, the shortest edge must be in the shortest path.''


To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes.
To reach the shortest path, Dijkstra always picks the shortest edge
leaving the known nodes. In each iteration, it finalizes the distance to
a node by picking the shortest one.


= Implementation =
= Implementation =
Line 15: Line 17:
         pi[v] = null
         pi[v] = null
     d[s] = 0
     d[s] = 0
    Q = V  // priority queue of nodes
     while Q is not empty:
     while Q is not empty:
         u = Q.extractMin()
         u = Q.extractMin()

Revision as of 06:06, 9 March 2024

Dijkstra's algorithm is a solution to the shortest path problem for graphs with positively-weighted edges.

Approach: Greedy

Dijkstra's algorithm centers around this property: of all the edges leaving the source, the shortest edge must be in the shortest path.

To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes. In each iteration, it finalizes the distance to a node by picking the shortest one.

Implementation

Dijkstra(G, w, s) {
    // initialize
    for all v in V:
        d[v] = infty
        pi[v] = null
    d[s] = 0
    Q = V   // priority queue of nodes
    while Q is not empty:
        u = Q.extractMin()
        for all v in adj[u]:
            if d[v] > d[u] + w(u,v):
                d[v] = d[u] + w(u,v)
                pi[v] = u