关于Dijkstra算法应用场景的验证及部分顶点对最短路径咨询

你的初始理解对不对？ #

先给你打个定心丸：你的核心理解是完全正确的！不过可以补充几个小细节让认知更完整：

• Dijkstra确实是处理无负权连通加权图最短路径的经典最优算法之一
• 它能覆盖两种核心场景：
  • 单源最短路径：从一个起点出发到所有其他顶点的最短路径（当然也包含任意两点间的，只要其中一个是起点）
  • 全顶点对最短路径：如果给每个顶点都单独跑一次Dijkstra，就能得到所有顶点之间的最短路径（不过这种场景如果顶点数不多，用Floyd-Warshall算法会更直接，但Dijkstra确实可行）
• 额外提一句：其实图不一定得是全连通的，只要起点能到达的子图是连通的就行，那些起点到不了的顶点，自然没法计算路径

能不能只跑一次就求解部分顶点对的最短路径？ #

这个得分情况看：

• 如果你关注的所有顶点对都是同一个起点（比如你要找A到B、A到D、A到G的路径），那绝对可以！只要以A为起点跑一次Dijkstra，就能得到A到所有其他顶点的最短路径，之后直接从结果里挑你需要的那几个顶点的路径就行，完全不用多跑
• 但如果你的部分顶点对是不同起点和终点的组合（比如要找A→B、C→D、E→F），那一次Dijkstra就搞不定了——因为Dijkstra是单源算法，一次运行只能输出一个起点到所有点的路径。这种情况下你有两个选择：
  1. 给每个不同的起点各跑一次Dijkstra，然后提取对应终点的结果就行
  2. 如果图的顶点数量不多，也可以试试Floyd-Warshall算法，一次运行就能得到所有顶点对的路径，之后再挑你需要的部分（不过这个算法时间复杂度是O(n³)，顶点多的话反而不如多次跑Dijkstra高效）

拿你举的例子来说：要是你关注的是A→C、A→H、A→K，那跑一次以A为起点的Dijkstra就搞定；但如果是A→B、C→E、G→J这种跨起点的组合，就得分别以A、C、G为起点各跑一次啦。

内容的提问来源于stack exchange，提问作者CCOthers