[从今天开始修炼数据结构]图的最短路径 —— 迪杰斯特拉算法和弗洛伊德算法的详解与Java实现
在网图和非网图中，最短路径的含义不同。非网图中边上没有权值，所谓的最短路径，其实就是两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，我们称路径上第一个顶点是源点，最后一个顶点是终点。
我们讲解两种求最短路径的算法。第一种，从某个源点到其余各顶点的最短路径问题。
1，迪杰斯特拉(Dijkstra)算法
迪杰斯特拉算法是一个按路径长度递增的次序产生最短路径的算法，每次找到一个距离V0最短的点，不断将这个点的邻接点加入判断，更新新加入的点到V0的距离，然后再找到现在距离V0最短的点，循环之前的步骤。有些类似之前的普里姆算法，是针对点进行运算，贪心算法。
这里我们首先约定，Vi在vertex[]中存储的index = i，以方便阐述思路。思路如下：
（1）我们拿到网图，如下.我们要找到从V0到V8的最短路径，使用邻接矩阵存储的图结构。我们寻找距离V0最近的顶点，找到了邻接点V1，距离是1，将其连入最短路径。
（2）修正与V1直接相关联的所有点到V0的最短路径。比如原本V2到V0的路径是5，现在通过V1，将其修改为1+3 = 4.，将V4置为6，V3置为8.我们现在就需要一个数组来存储每个点到V0的最短路径了。我们设置一个数组ShortPathTable[numVertex]来存储。
同时我们还需要存储每个点到V0的最短路径，为此我们设置一个数组Patharc[numVertex]，P[i] = k表示Vi到V0的最短路径中，Vi的前驱是Vk。我们还需要一个数组来存储某个顶点是否已经找到了到V0的最短路径，为此我们设置finals[numVertex]。此时
S[] = { 0 , 1 , 4 , 8 , 6 , I , I , I , I } P[] = { 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 } f[] = { 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 }（3）此时拿到与V0距离最短的点（还没有加入最短路径的，即final[i] = 0的点），这里是V2，然后更新V2的邻接点V4，V5到V0的最短路径分别为1+3+1=5和1+3+7=11，并将V2加入最短路径
S[] = { 0 , 1 , 4 , 8 , 5 , I , I , I , I } P[] = { 0 , 0 , 1 , 1 , 2 , 0 , 0 , 0 , 0 } f[] = { 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 } 
接下来的步骤跟前面类似，我就不再重复了，大家应该也理解迪杰斯特拉算法的步骤了，下面来看代码实现。
public void ShortestPath_Dijkstra(){ int[] ShortPathTable= new int[numVertex]; int[] Patharc = new int[numVertex]; int[] finals = new int[numVertex]; //初始化 for (int i = 0; i < numVertex; i++){ ShortPathTable[i] = edges[0][i]; //初始化为v0的邻接边 Patharc[i] = 0; finals[i] = 0; } finals[0] = 1; //v0无需找自己的邻边 int minIndex = 0; //用来保存当前已经发现的点中到V0距离最短的点 for (int i = 1; i < numVertex; i++){ //找到目前距离V0最近的点 int min = INFINITY; for (int index = 0; index < numVertex; index++){ if (finals[index] != 1 && ShortPathTable[index] < min){ minIndex = index; min = ShortPathTable[index]; } } finals[minIndex] = 1; //更新还未加入最短路径的点到V0的距离 for (int index = 0; index < numVertex; index++){