如何找到至少通过一个强制节点的两个节点之间的最短距离？
how to find the shortest distance between two nodes that pass at least one of the compulsory nodes?
我有一个包含大约 5000 个节点的双向加权图
我有一个 "important" 节点的列表（大约 100 个）。给定一个起始节点和一个结束节点，我如何找到这两个节点之间至少通过 "important" 个节点中的一个的最短距离。请注意，没有负边缘。我实现了 dijkstra 算法来找到给定两个节点的最短距离。我知道如何解决这个问题的唯一方法是遍历重要节点列表，找到所有重要节点从开始 -> 重要节点#1 -> 结束的距离，然后取最小值。有没有更快的方法来解决这个问题？
您的方法完全正确，您需要的是应用 Dijkstra 的次数较少。
这个问题只要应用两次 Dijkstra 就可以轻松解决。
以 start 为源应用 Dijkstra。将距离存储在数组 fromS.
再应用一次 Dijkstra。这次以end为来源。将距离存储在数组 toE 中。
由于您的图是无向的，从 end 节点到每个其他节点的最短距离与从每个其他节点到 end 节点的最短距离相同。 （这就是诀窍）。
找到所需的最短距离。
For node in importantNodes :
ans = min ( fromS [node] + toE[node] , ans)
return ans
我有一个包含大约 5000 个节点的双向加权图 我有一个 "important" 节点的列表（大约 100 个）。给定一个起始节点和一个结束节点，我如何找到这两个节点之间至少通过 "important" 个节点中的一个的最短距离。请注意，没有负边缘。我实现了 dijkstra 算法来找到给定两个节点的最短距离。我知道如何解决这个问题的唯一方法是遍历重要节点列表，找到所有重要节点从开始 -> 重要节点#1 -> 结束的距离，然后取最小值。有没有更快的方法来解决这个问题？
您的方法完全正确，您需要的是应用 Dijkstra 的次数较少。 这个问题只要应用两次 Dijkstra 就可以轻松解决。
以 start 为源应用 Dijkstra。将距离存储在数组 fromS.
中
再应用一次 Dijkstra。这次以end为来源。将距离存储在数组 toE 中。 由于您的图是无向的，从 end 节点到每个其他节点的最短距离与从每个其他节点到 end 节点的最短距离相同。 （这就是诀窍）。
找到所需的最短距离。
For node in importantNodes : ans = min ( fromS [node] + toE[node] , ans) return ans