最短路径问题

1.单元最短路径

注：带权路径长度——当图是带权图时，一条路径上所有的权值之和，称为该路径的带权路径长度

1.BFS算法（无权图）

BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图。

2.Dijkstra算法

• 1.初始：选择从任意一个顶点开始，初始化三个数组信息如下。

1.标记各顶点是否已找到最短路径，记数组final[10]
2.记录最短路径长度数组为dist[10]
3.记录当前路径上的前驱数组为path[10]

• 2.循环遍历所有结点，找到还没有确定最短路径，且dist最小的顶点Vi，令final[i]=是。
  检查所有邻接自Vi的顶点，若其final值为否，则更新dist和path数组。

• 3.循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点Vi，令final[i]=是。
  检查所有邻接自Vi

• 4.结论
  Dijkstra算法不适于有负权值的带权图。

3.Floyd算法

问题：求出每一对顶点之间的最短路径
解决：使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点Vi->Vj之间的最短路径可分为如下几个阶段:

• 1.初始：不允许在其他顶点中转，最短路径是？
• 2.第1步：若允许在V0中转，最短路径是？
• 3.第2步：若允许在V0，V1中转，最短路径是？
• 4.第3步：若允许在V0，V1，V2中转，最短路径是？
• 5，6,7........
• n.第(n-1)步：若允许在V0，V1，V2，....V(n-1)中转，最短路径是？

代码实现

// 主要实现，side数组存储的是各顶点之间的边
  for(int k=0; k<n; k++){  // 动态的考虑以某个顶点为中转点
    for(int i=0; i<n; i++){  // 遍历整个矩阵，i为行号，j为列号
      for(int k=0; j<n; j++){
        if(side[i][j] > side[i][k] + side[k][j]){  // 以当前顶点为中转点的路径更短
          side[i][j] = side[i][k] + side[k][j];  // 更新最短路径长度
          path[i][j] = k;  // 中转点
        }
      }
    }
  }

结论
可以解决负权值的带权图，但是不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径。

4.3种最短路径算法总结