CODEWITHSUNDEEP
algorithmtime-complexitypseudocodedijkstrashortest-path
VeryLazyBoy
VeryLazyBoy

Reputation: 420

Dijkstra's algorithm- why every time extract the vertex with smallest priority?

I am learning Dijkstra's algorithm to find shortest path. And I noticed that there is a priority queue to help extract the vertex with lowest priority in the vertex set. Will the algorithm still work if I pick a vertex regardless of priority, instead of the one with lowest priority, from the vertex set? If yes, what about the time complexity?

The original Dijkstra's algorithm from Wikipedia is like:

function Dijkstra(Graph, source):
    dist[source] ← 0                                

    create vertex set Q

    for each vertex v in Graph:           
        if v ≠ source
            dist[v] ← INFINITY                      
            prev[v] ← UNDEFINED                     

    Q.add_with_priority(v, dist[v])


    while Q is not empty:                          
        u ← Q.extract_min()                        
        for each neighbor v of u:                  
            alt ← dist[u] + length(u, v) 
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u
                Q.decrease_priority(v, alt)

    return dist[], prev[]

After making modifications to pick a vertex regardless of priority(please note that there is an "add" after relaxation):

function DijkstraVariant(Graph, source):
    dist[source] ← 0                                

    create vertex set Q

    for each vertex v in Graph:           
        if v ≠ source
            dist[v] ← INFINITY                      
            prev[v] ← UNDEFINED                     

    Q.just_add(v)                  // Don't care about the priority


    while Q is not empty:                          
        u ← Q.random_pick()         // Don't care about the priority        
        for each neighbor v of u:                 
            alt ← dist[u] + length(u, v) 
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u
                Q.just_add(v)  // Don't care about the priority

    return dist[], prev[]

Upvotes: 0

Views: 430

Answers (1)

Ext3h
Ext3h

Reputation: 6391

No, it will not work. It will yield a path, but it is no longer guaranteed to be the shortest.

The priority is required to account for non uniform weights, with a plain FIFO queue it will only work if all edge weights are equal. It becomes a plain broad first search.

With a random selection, instead of priority, the algorithm detoriates further, down to the level of a depth first search. That also removes all the guarantees the BFS provided, such as finding any existing path even in infinite graphs in finite time.

Upvotes: 4

Related Questions