Running Dijkstra Algorithm-CodePudding

Given a graph like this one:

         A
        ^ ^
       /   \
      3     4
     /       \
    B -- 5 -> C

E={(B,A)(C,A)(B,C)}

What happens if we run Dijkstra on node A?

A is initialized to 0, B and C to infinity, but A doesn't points anywhere.

So then we choose randomly between B and C? Or the algorithm doesn't work in that case?

Thanks!

CodePudding user response：

Dijkstra will still run and give you the right answer for this graph. If you so choose you can initialize the queue with just the start node and add or update neighbors to/in the queue as you explore them. In this case the algorithm will just terminate after one iteration of extracting (A) from the queue and exploring its zero neighbors, appropriately leaving the distances to B and C as infinity (with no prev nodes) and leaving A's path zero. If you think about it, this is the desired answer, as there are no paths from A to B or C.

Or, if you implement it as in Wikipedia, adding every node to the queue at the start, it will still produce the same results.

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph:          
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9              prev[v] ← UNDEFINED                // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u]   length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

After extracting A and exploring it's nonexistent neighbors, nothing is updated. It will then arbitrarily choose between B and C to extract next as they have the same distance (not 'randomly' of course, just depending on how you initialize/extract from your queue).

When it checks B, it will see it can get to C in Infinity 5, not any better than the current distance to C of Infinity so nothing updates, and to A in Infinity 3, not better than A's current distance of 0.

When it checks C, it will see it can get to A in Infinity 4, not better than the current distance to A of 0, so nothing updates.

Then the queue is empty and the same result of dist[A] = 0, dist[B] = dist[C] = Infinity is returned.

So a correct implementation of Dijkstra will be able to handle such a graph (as it should any directed graph with non-negative weights).