How does boost graph dijkstra_shortest_paths pick the shortest path when there are multiple shortest paths between a specific pair of nodes?

user_14018440 0
Viewed 86

I have an unweighted, undirected network of around 50000 nodes, from this network I need to extract the shortest path between any pair of nodes. I used the dijkstra_shortest_paths function from the boost library and it worked fine. Later I realised that between a given pair of nodes A and B, there can be more than one shortest path. In this case, how does the Dijkstra function pick among these shortest paths? Is it dependent on the node ids or the order of how these nodes are stored in the memory?

I found a few questions asking about how to extract all of the shortest paths between two nodes as normally only one of them is extracted, for example this question and this question. However, I don't want to extract all of the shortest paths between two nodes. Instead, I want to know how exactly the very path returned by the function is picked up among other shortest paths that have the same length.

I tried to have a deeper look into the related source code within the boost library, but it seems it is too advanced for me and I got lost soon. Also, I couldn't find an answer by googling, so I ask here.

shortest-path dijkstra graph boost c++
1 Answers

The exact algorithm is documented:

DIJKSTRA(G, s, w)
  for each vertex u in V (This loop is not run in dijkstra_shortest_paths_no_init)
    d[u] := infinity
    p[u] := u
    color[u] := WHITE
  end for
  color[s] := GRAY
  d[s] := 0
  INSERT(Q, s)
  while (Q != Ø)
    u := EXTRACT-MIN(Q)
    S := S U { u }
    for each vertex v in Adj[u]
      if (w(u,v) + d[u] < d[v])
        d[v] := w(u,v) + d[u]
        p[v] := u
        if (color[v] = WHITE)
          color[v] := GRAY
          INSERT(Q, v)
        else if (color[v] = GRAY)
          DECREASE-KEY(Q, v)
      else
        ...
    end for
    color[u] := BLACK
  end while
  return (d, p)

In the linked page it highlights where events happen.

It follows that the order in which vertices are discovered dictates your answer.

You can achieve other tie-breakers without modifying the graph by specifying a custom comparison (CompareFunction).

user_853710
Related