【算法】图的最短路径(Floyd算法)
现在离考研还不到100天了，杜绝胡思乱想，活在现实中~不过我发现算法的文章阅读量不高啊，是不是我说的不好呢~如果哪里需要改进的各位可以评论区留言。还是现在都比较注重应用层面了呢？
今天总结的是图的最短路径的另外一种算法—-弗洛伊德算法。与前面迪杰斯特拉算法不同的是，弗洛伊德算法求的是图中任意一对顶点之间的最短路径，当然，仍然针对有向带权图。
我们就先直接进入算法的演算过程吧~大家可以在这个演算过程中，体会到弗洛伊德算法是如何表示任意两点间的最短路径的。
算法准备：
1、图的邻接矩阵(与以往不同的是，主对角线，也就是自身到自身，这次我们不使用无穷大表示，而是采用0。书上和习题中是这样的，我们就入乡随俗吧~)
2、二维数组A，用于存放任意一对顶点之间的最短路径权值。
3、二维数组Path，用于存放任意一对顶点之间的最短路径。每个单元格的内容表示从i点到j点途经的顶点。
算法过程：
1、初始化过程：将邻接矩阵copy到二维数组A中，将二维数组Path中所有元素填充为-1(都没有开始寻找，哪里来的中间顶点呢)。
2、列出顶点的所有可能二元组，自己到自己不算。这里为
{0，1}，{0，2}，{0，3}，{1，0}，{1，2}，{1，3}，{2，0}，{2，1}，{2，3}，{3，0}，{3，1}，{3，2}
3、选择编号为0的点为中间点，从【2】中二元组集合的第一个元素开始，执行以下过程
3.1：用i，j两个变量分别指向二元组里的两个元素，比如\{0，1\}这个二元组，i指向0；j指向13.2：判断A\[i\]\[j\] > A\[i\]\[0\] + A\[0\]\[j\]吗？如果表达式为真，进入3.3；若为假，则结束本次过程，进入下一个二元组3.3：更新A\[i\]\[j\]的值为A\[i\]\[0\] + A\[0\]\[j\]，Path\[i\]\[j\]的值为0
分析：步骤3其实挺形象的，也是算法核心。二维数组A就是图邻接矩阵的copy，我们以行的角度来看这个矩阵，比如A[0][1] = 5，表示从顶点0到顶点1有一条边相连，权值为5。而在这次循环中，我们选择了0为中间点，把步骤3.2的表达式翻译过来就是说：从i点到j点的代价会大于从i点到0点，再从0点到j点的代价吗？是不是非常形象地把顶点0作为中间点这个思想表示出来了呢？如果满足3.2中的表达式，就表示我经过中间点0到目的地比我直接去目的地的代价还要来的少，于是我们更新A[i][j]的值为新求出的这个比原来小的代价的值，Path[i][j]的值更新为0，就表示从i点到j点，要经过0点。非常巧妙地记录了路径。(PS.这怎么有点向我以前看过的深度优先搜索走迷宫村路径的方式呀~，这个与数学中的定积分的某一条性质也特别像。)
4、重复步骤【3】，直到所有的顶点都做过一次中间点为止。
最后两个矩阵的值如下：
下面一个步骤就是找出两点间的路径了，比如顶点1到顶点0，我们看数组Path
Path[1][0] = 3，说明顶点3是途径顶点
Path[3][0] = 2，说明顶点2是途径顶点
Path[2][0] = -1，说明顶点2到顶点0没有途径顶点，也就是说，可以由顶点2直接到顶点0，即它们有边连接。
所以，序列为1->3->2->0，显然，这是一个逐层递进，递归的过程。
下面上代码：
1、图的结构体定义：
#define Max 100typedef struct graph *Graph;typedef struct graph{int e , n;int data[Max][Max];}graph;
2、核心算法
void Floyd(Graph g , int Path[][Max]){int i , j , k;int A[Max][Max];for(i = 0 ; i < g->n ; i++){for(j = 0 ; j < g->n ; j++){A[i][j] = g->data[i][j];Path[i][j] = -1;}}for(i = 0 ; i < g->n ; i++){for(j = 0 ; j < g->n ; j++){for(k = 0 ; k < g->n ; k++){if(A[j][k] > A[j][i] + A[i][k]){A[j][k] = A[j][i] + A[i][k];Path[j][k] = i;}}}}}
3、输出路径
void showPath(int Path[][Max] , int res , int des){if(Path[res][des] != -1){printf("%d ",Path[res][des]);int mid = Path[res][des];// showPath(Path,res,mid);showPath(Path,mid,des);}else{printf("%d",des);}}
运行效果如下
做一个说明：第一行输入两个数，表示总共有几个顶点(从0开始计算)，还有几条边。
边的结构是这样的：总共三个数值，第一个表示起点，第二个表示终点，第三个表示边权值。边输入完成后紧接着输入两个数，表示要查找的哪两个顶点直接的最短路径。
Love The Way You Lie
忘是亡心i
╰+攻爆jí腚メ
港控/mmm°
还没有评论，来说两句吧...