如何找到通过至少一个强制节点的两个节点之间的最短距离？

我有一个具有约5000个节点的双向加权图表我有一个“重要”节点（100左右）列表。给定一个起始节点和一个结束节点，如何找到这两个节点之间的最短距离，这两个节点至少通过一个“重要”节点。请注意，没有负面的边缘。我实现了dijkstra的算法来找到给定两个节点的最短距离。我知道如何解决这个问题的唯一方法是查看重要节点列表，找到所有重要节点从开始 - >重要节点＃1 - >结束的距离，然后取最小值。有没有更快的方法来解决这个问题？如何找到通过至少一个强制节点的两个节点之间的最短距离？

来源

2017-09-29 abc

你的方法是绝对正确的，你需要的是应用Dijkstra更少的次数。这个问题很容易通过应用Dijkstra两次来解决。

应用Dijkstra算法与开始源。将数组中的距离从S中存储。
再次申请Dijkstra。这次以结束作为来源。将数组中的距离存储到E。由于你的图是无向最短距离从端节点到每个其他节点是相同的最短距离从每个其他节点到端节点。（这是诀窍）。

找到需要的最短距离。

For node in importantNodes : 
    ans = min (fromS [node] + toE[node] , ans) 
return ans

来源

2017-10-02 19:33:48 Nidheesh

如何找到通过至少一个强制节点的两个节点之间的最短距离？

回答

相关问题