CODEWITHSUNDEEP
algorithmdijkstra
Bunny Rabbit
Bunny Rabbit

Reputation: 8411

Question about Dijkstra's algorithm implementation on Wikipedia

function Dijkstra(Graph, source):
    for each vertex v in Graph:            // Initializations
        dist[v] := infinity ;              // Unknown distance function from source to v
        previous[v] := undefined ;         // Previous node in optimal path from source
    end for ;
    dist[source] := 0 ;                    // Distance from source to source
    Q := the set of all nodes in Graph ;
    // All nodes in the graph are unoptimized - thus are in Q
    while Q is not empty:                  // The main loop
        u := vertex in Q with smallest dist[] ;
        if dist[u] = infinity:
            break ;                        // all remaining vertices are inaccessible from source
        fi ;
        remove u from Q ;
        for each neighbor v of u:          // where v has not yet been removed from Q.
            alt := dist[u] + dist_between(u, v) ;
            if alt < dist[v]:              // Relax (u,v,a)
                dist[v] := alt ;
                previous[v] := u ;
            fi ;
        end for ;
    end while ;
    return dist[] ;
end Dijkstra.

the above algorithm has been mentioned in Wikipedia for Dijkstra shortest path. What I am not able to understand here is that, while we have set the distances to all the vertices as infinity [line number 3], at line 9 we are assigning u := vertex in Q with smallest dist[] but since all the distances are infinite (as set in line number 3) how can there be a smallest distance?

Upvotes: 1

Views: 2493

Answers (3)

Gabe
Gabe

Reputation: 86818

In line 6 it says dist[source] := 0 which makes one of the distances non-infinite. Once that is removed, successive iterations of the loop set dist[v] := alt, creating more non-infinite distances.

Upvotes: 2

munificent
munificent

Reputation: 12374

In line 6, the distance to the start node is set to zero. Everything proceeds from there.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373402

The idea behind Dijkstra's algorithm is that initially, you don't know the distances to any of the nodes in the graph, so you set them all to infinity. However, as the algorithm proceeds, it grows a sort of "ball" outward from the start node of nodes where there is an estimate of the distance. Initially, you set the estimated distance of the start node from itself to be 0, since it's trivially reachable from itself after traveling no distance at all. This is why the algorithm is well-defined - initially, you have some node to which you know the distance, and whenever you visit a node and expand it, you decrease the distance to all of that node's neighbors by considering the effects of the edges leaving that node.

Interestingly, though, there is a case where you could end up with some of those distances being infinity. Notably, if some node v is not reachable from the start node, then its distance never decreases, and Dijkstra's algorithm will report it at distance infinity from the source node.

Another important detail is that in the event of a tie in the distances, you can break that tie arbitrarily. Dijkstra's algorithm works just fine in that case. If you really are opposed to this idea, you can artificially break all the ties by adding a very small number to all of the edge costs.

Upvotes: 0

Related Questions