У меня есть невзвешенная, ненаправленная сеть из примерно 50000 узлов, из этой сети мне нужно извлечь кратчайший путь между любой парой узлов. Я использовал функцию dijkstra_shortest_paths из библиотеки boost, и она работала нормально. Позже я понял, что между заданной парой узлов А и Б может быть более одного кратчайшего пути. Как в этом случае функция Дейкстры выбирает среди этих кратчайших путей? Зависит ли это от идентификаторов узлов или порядка хранения этих узлов в памяти?
Я нашел несколько вопросов о том, как извлечь все кратчайшие пути между двумя узлами, поскольку обычно извлекается только один из них, например этот вопрос и этот вопрос. Однако я не хочу извлекать все кратчайшие пути между двумя узлами. Вместо этого я хочу знать, как именно тот самый путь, который возвращает функция, выделяется среди других кратчайших путей той же длины.
Я попытался глубже изучить соответствующий исходный код в библиотеке boost, но кажется, что это слишком сложно для меня, и вскоре я заблудился. В гугле ответа тоже не нашел, поэтому спрошу здесь.
Точный алгоритм задокументировано:
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)
На связанной странице выделяется место, где происходят события.
Отсюда следует, что порядок, в котором обнаруживаются вершины, диктует ваш ответ.
Вы можете добиться других результатов, не изменяя график, указав пользовательское сравнение (CompareFunction
).