undirected graph中两优质节点间最短路径求解咨询

这是个很常见的图论问题，根据你的图的规模和边权特性，我推荐下面几种实用的解法：

方法1：多源Dijkstra算法（非负权边首选） #

如果你的图中所有边的权重都是非负数，这是效率最高的解法：

• 首先初始化一个距离数组dist，把所有节点的距离设为无穷大（比如用一个极大值INF表示）。
• 把所有优质节点都加入最小优先队列（堆结构），同时将这些优质节点的dist值设为0，还要记录每个节点是否是优质节点。
• 按照Dijkstra的标准流程处理：每次从队列中取出距离最小的节点u，遍历它的所有邻接节点v。如果dist[v] > dist[u] + weight(u, v)，就更新dist[v]为这个更小的值，并把v加入队列。
• 在遍历过程中，每当我们取出一个优质节点v且它的dist[v]不为0（说明它不是初始加入队列的源节点），此时的dist[v]就是从某个优质节点到v的最短路径长度。我们维护一个全局最小值，每次遇到这样的情况就更新这个最小值。
• 当队列处理完毕后，这个全局最小值就是你要找的两个优质节点间的最短路径长度。如果最小值还是无穷大，说明没有两个优质节点连通，返回-1即可。

方法2：Floyd-Warshall算法（小规模图/任意权边） #

如果你的图节点数量不多（比如n≤1000），或者存在负权边但没有负环，这个方法实现起来最省心：

• 先初始化一个二维数组d，d[i][j]表示节点i到节点j的最短路径长度。初始时，d[i][j]设为无穷大，d[i][i]设为0，然后对于每条边(u, v)，把d[u][v]和d[v][u]设为边的权重（因为是无向图）。
• 运行Floyd-Warshall的核心三重循环：

  for k in range(n):
      for i in range(n):
          for j in range(n):
              if d[i][j] > d[i][k] + d[k][j]:
                  d[i][j] = d[i][k] + d[k][j]
  

• 遍历所有优质节点对(u, v)（注意u≠v，避免重复计算），找出d[u][v]中的最小值，就是答案。如果所有优质节点对的距离都是无穷大，说明没有连通的优质节点对。

方法3：单源Dijkstra批量计算（中等规模图） #

如果图的节点数量不算特别大，但多源Dijkstra实现起来有点麻烦，也可以对每个优质节点单独跑一次单源Dijkstra：

• 遍历每个优质节点s，以s为源点跑Dijkstra，得到s到所有其他节点的最短距离。
• 对于每个其他优质节点t，记录s到t的距离，维护全局最小值。
• 最后这个最小值就是答案。这种方法的时间复杂度是O(k*(m + n log n))，其中k是优质节点的数量，m是边数，适合k不大的情况。

边界情况要注意 #

• 如果优质节点的数量小于2，直接返回“不存在符合条件的路径”；
• 如果图中有直接连接两个优质节点的边，记得优先检查这类边的权重，可能它就是最短路径；
• 如果部分优质节点处于不同的连通分量，只需要考虑同一连通分量内的优质节点对。

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