经典算法之最短路径问题
定义
所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。
重要概念
图的路径：图G =中，从任一顶点开始，由边或弧的邻接至关系构成的有限长顶点序列称为路径。注意：有向图的路径必须沿弧的方向构成顶点序列；构成路径的顶点可能重复出现(即允许反复绕圈)。
路径长度：路径中边或弧的数目。
简单路径：除第一个和最后一个顶点外，路径中无其它重复出现的顶点，称为简单路径。
回路或环：路径中的第一个顶点和最后一个顶点相同时，称为回路或环。
图的最短路径：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
Dijkstra（迪杰斯特拉）算法
它的算法思想是按路径长度递增的次序一步一步并入来求取，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径问题。
给定一个带权有向图，再给定图中一个顶点（源点），求该点到其他所有点的最短距离，称为单源最短路径问题。
如下图，求点1到其他各点的最短距离
准备工作：
以下为该题所需要用到的数据
int N; //保存顶点个数
int M; //保存边个数
int max; //用来设定一个比所有边的权都大的值，来表示两点间没有连线
int[] visit; //找到一个顶点的最短距离，就把它设为1，默认为0（即还没有找到）
int[][] distance; //保存图中个边的值，两点间无边则设为max
int[] bestmin; //保存源点到其他各点的最短距离，用于最后输出
String[] path; //有些题目会要求输出路径，保存输出路径
算法步骤：
①找出与源点距离最短的那个点，即遍历distance[1][1]，distance[1][2],…distance[1][N]中的最小值，如题：
源点1到2,4,5的距离分别为10,30,100,。3无法直接到达即此时distance[1][3] = max。那么这一步找出的点就是
顶点2。此时distance[1][2]即为源点1到顶点2的最短距离。将visit[2]设为1（顶点2完成）。
②松弛操作，
以①找出的点作为中心点（此时为顶点2），去遍历visit[i]为0的点，如果distance[1][2] + distance[2][i] < distance[1][i]
就把新的较短路径赋值给它，即distance[1][i] = distance[1][2] + distance[2][i]，
此时顶点2能到达的点只有顶点3，并且distance[1][3] = max ，所以更新distance[1][3]的值为distance[1][2] + distance[2][3] = 60
完成以上两个步骤后回到步骤①，即这是个循环，每次循环能找出一个最短距离的点和更新其他点，所以该循环要遍历
N-1次就可以把所有点最短距离找出，大概过程如下：
for(int i = 2; i <= N; i++) {
步骤①（在一个循环内找到距离最短的点）
步骤②（以①找到的点为中心，通过一个循环更新所有visit[i]为0的点到源点的距离）
}
完整代码如下：
import java.util.Scanner;
public class Dijkstra__Single_Source_Shortest_Path {
private static int N;
private static int M;
private static int max;
private static int[] visit;
private static int[][] distance;
private static int[] bestmin;
private static String[] path;
public static void Dijkstra() {
visit[1] = 1;
bestmin[1] = 0;
//大循环（搞定这里就算搞定该算法了，后面的输出什么的可以不看）
for(int l = 2; l <= N; l++) {
int Dtemp = max;
int k = -1;
//步骤①
for(int i = 2; i <= N; i++) {
if(visit[i] == 0 && distance[1][i] < Dtemp) {
Dtemp = distance[1][i];
k = i;
}
}
visit[k] = 1;
bestmin[k] = Dtemp;
//步骤②
for(int i = 2; i <= N; i++) {
if(visit[i] == 0 && (distance[1][k] + distance[k][i]) < distance[1][i]) {
distance[1][i] = distance[1][k] + distance[k][i];
path[i] = path[k] + "-->" + i;
}
}
}
//输出路径
for(int i=1;i<=N;i++) {
System.out.println("从"+1+"出发到"+i+"的最短路径为："+path[i]);
}
System.out.println("=====================================");
for(int i = 1; i <= N; i++) {
System.out.println("从1出发到" + i + "点的最短距离为：" + bestmin[i]);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
System.out.print("请输入节点个数N，路径总数M：");
N = input.nextInt();
M = input.nextInt();
max = 10000;
bestmin = new int[N+1];
distance = new int [N+1][N+1];
visit = new int[N+1];
path=new String[N+1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if(i == j) {
distance[i][j] = 0;
}else {
distance[i][j] = max;
}
}
bestmin[i] = max;
path[i] = new String("1-->" + i);
}
System.out.println("请输入" + M +"条数据x，y，z（表示x点到y点的距离为z）：");
for(int i = 1; i <= M; i++) {
int x = input.nextInt();
int y = input.nextInt();
int z = input.nextInt();
distance[x][y] = z;
}
input.close();
Dijkstra();
}
}
运行结果如下：
Floyd（弗洛伊德）算法
Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。（动态规划算法是通过拆分问题规模，并定义问题状态与状态的关系，使得问题能够以递推（分治）的方式去解决，最终合并各个拆分的小问题的解为整个问题的解。）
算法思想
从任意节点i到任意节点j的最短路径不外乎2种可能：
1)直接从节点i到节点j，
2)从节点i经过若干个节点k到节点j。
所以，我们假设arcs(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j)，这样一来，当我们遍历完所有节点k，arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。（由于动态规划算法在执行过程中，需要保存大量的临时状态（即小问题的解），因此它天生适用于用矩阵来作为其数据结构，因此在本算法中，我们将不使用Guava-Graph结构，而采用邻接矩阵来作为本例的数据结构）
算法分析及描述
假设现要求取如下示例图所示任意两点之间的最短路径：
我们以一个4x4的邻接矩阵（二维数组arcs[ ][ ]）作为图的数据结构。比如1号节点到2号节点的路径的权值为2，则arcs[1][2] = 2，2号节点无法直接到达4号节点，则arcs[2][4] = ∞(Integer.MAX_VALUE)，则可构造如下矩阵：
根据以往的经验，如果要让任意两个顶点（假设从顶点a到顶点b）之间的距离变得更短，唯一的选择就是引入第三个顶点（顶点k），并通过顶点k中转（a -> k ->b）才可能缩短顶点a到顶点b之间的距离。
于是，现在的问题便分解为：求取某一个点k，使得经过中转节点k后，使得两点之间的距离可能变短，且还可能需要中转两个或者多个节点才能使两点之间的距离变短。比如图中的4号节点到3号节点（4 -> 3）的距离原本是12（arcs[4][3] = 12），如果在只通过1号节点时中转时（4 -> 1 ->3），距离将缩短为11（arcs[4][1] + arcs[1][3] = 5 + 6 = 11）。
其实1号节点到3号节点也可以通过2号节点中转，使得1号到3号节点的路程缩短为5（arcs[1][2] + arcs[2][3] = 2 + 3 = 5），所以如果同时经过1号和2号两个节点中转的话，从4号节点到3号节点的距离会进一步缩短为10。
于是，延伸到一般问题：
1、当不经过任意第三节点时，其最短路径为初始路径，即上图中的邻接矩阵所示。
2、当只允许经过1号节点时，求两点之间的最短路径该如何求呢？只需判断arcs[i][1]+arcs[1][j]是否比arcs[i][j]要小即可。arcs[i][j]表示的是从i号顶点到j号顶点之间的距离，arcs[i][1] + arcs[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。循环遍历一遍二维数组，便可以获取在仅仅经过1号节点时的最短距离，实现如下：
for (int i = 1; i <= vexCount; i++) {
for (int j = 1; j < vexCount; j++) {
if (arcs[i][1] + arcs[1][j] < arcs[i][j]) {
arcs[i][j] = arcs[i][1] + arcs[1][j];
}
}
}
由于上述代码更新了两点之间经过1号节点的最短距离arcs[i][j]，因此，数组中每两个节点之间对应距离都是最短的。由于此时arcs[i][j]的结果已经保存了中转1号节点的最短路径，此时如果继续并入2号节点为中转节点，则是任意两个节点都经过中转节点1号节点和2号节点的最短路径，因为运算完中转1号节点时，arcs[i][j]的结果已经更新为中转1号节点的最短路径了。
更一般的，继续并入下一个中转节点一直到vexCount个时，arcs[i][j]的结果保存的就是整个图中两点之间的最短路径了。这就是Floyd算法的描述，变成代码就是下面几行行：
for (int k = 1; k <= vexCount; k++) { //并入中转节点1,2,...vexCount
for (int i = 1; i <= vexCount; i++) {
for (int j = 1; j < vexCount; j++) {
if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {
arcs[i][j] = arcs[i][k] + arcs[k][j];
path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息
}
}
}
}
对应到示例图的中间运算结果如下：
print array step of 1: //并入1号节点的结果
0 2 6 4
∞ 0 3 ∞
7 9 0 1
5 7 11 0
print array step of 2: //并入2号节点的结果
0 2 5 4
∞ 0 3 ∞
7 9 0 1
5 7 10 0
print array step of 3: //并入3号节点的结果
0 2 5 4
10 0 3 4
7 9 0 1
5 7 10 0
print array step of 4: //并入4号节点（图最终两两节点之间的最短路径值）
0 2 5 4
9 0 3 4
6 8 0 1
5 7 10 0
虽然此时已求得了节点的最短路径，但结果却不能明显的表达最终最短路径是中转了哪些节点，因此这里对应到动态规划算法中的强项——算法过程中可以完全记录所有的中间结果。我们再定义一个二位数组path[][]，其大小规模对应arcs[][]，初始结果path[i][j] = j，表示节点i到节点j最后的中转节点是j。在运算中是在判断arcs[i][k]+arcs[k][j]比arcs[i][j]要小时，我们进一步更新为：path[i][j] = path[i][k]，即当前最短路径的最后中转节点是path[i][k]对应的节点（如果只允许中专一个节点时即为k，但中转多个节点时，需要对应上一步的中转节点，因此这里要指明是path[i][k]而不是k）。 于是我们通过向前递推path[][]数组，直到path[i][j]是目标节点。则可输出其中转节点，输出函数实现如下：
private void printPath(int arcs[][], int path[][], int vexCount) {
int temp;
for (int i = 1; i <= vexCount; i++) {
StringBuilder builder = new StringBuilder();
for (int j = 1; j <= vexCount; j++) { //遍历打印任意亮点的路径
builder.append(i).append("->").append(j)
.append(", weight: "). append(arcs[i][j])
.append(":").append(i);
temp = path[i][j];
while(temp != j) {
builder.append("->").append(temp);
temp = path[temp][j];
}
builder.append("->").append(j).append("\n");
}
Log.i(TAG, builder.toString());
}
}
对应示例图的最短路径的中转节点结果输出如下：
1->1, weight: 0, path: 1->1
1->2, weight: 2, path: 1->2
1->3, weight: 5, path: 1->2->3
1->4, weight: 4, path: 1->4
2->1, weight: 9, path: 2->3->4->1
2->2, weight: 0, path: 2->2
2->3, weight: 3, path: 2->3
2->4, weight: 4, path: 2->3->4
3->1, weight: 6, path: 3->4->1
3->2, weight: 8, path: 3->4->1->2
3->3, weight: 0, path: 3->3
3->4, weight: 1, path: 3->4
4->1, weight: 5, path: 4->1
4->2, weight: 7, path: 4->1->2
4->3, weight: 10, path: 4->1->2->3
4->4, weight: 0, path: 4->4
具体Floyd算法的示例demo实现，
请参考：https://github.com/Jarrywell/GH-Demo/blob/master/app/src/main/java/com/android/test/demo/graph/Floyd.java
参考文档
https://blog.csdn.net/junya_zhang/article/details/83617762
https://www.jianshu.com/p/92e46d990d17
https://www.cnblogs.com/thousfeet/p/9229395.html
https://www.cnblogs.com/zhanghongcan/p/8684465.html
https://www.cnblogs.com/wangyuliang/p/9216365.html
腾讯云开发者
