Floyd求最短路径算法详解

Floyd求最短路径算法详解2013-05-24倘若我们要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。其实现最基本的功能，求出任意两点间的最短路径，

求最短路径的经典方法有很多种，最常用的便是迪杰斯特拉算法和佛洛依德（Floyd）算法，这篇文章就着重介绍Floyd算法。

求两点之间的最短路径无外乎有两种情况，一种就是从一点直接到另一点，另一种就是从一点经过n个节点后再到另一个节点，比如说要从A到B，则有两种情况就是A直接到B，或者是从A经过N个节点后再到B，所以，我们假设Dis（AB）为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis（AX）+Dis（XB）<Dis（AB）是否成立，如果成立，证明从A再到B的路径比A直接到B的路径短，我们便设置Dis（AB）=Dis（AX）+Dis（XB）,这样一来，当我们遍历完所有节点X，Dis（AB）中记录的便是A到B的最短路径的距离。

直接上代码：

for（k = 0; k < Number; ++k）{for（i = 0; i < Number; ++i）{for（j = 0; j < Number; ++j）{if（（Dis[i][k] + Dis[k][j]） < Dis[i][j]）{// 找到更短路径Dis[i][j] = Dis[i][k] + Dis[k][j];}}}}

那么接下来的问题就是，我们如何找出最短路径呢？这里需要借助一个辅助数组Path，它是这样使用的：Path（AB）的值如果为P，则表示A节点到B节点的最短路径是A->...->P->B。这样一来，假设我们要找A->B的最短路径，那么就依次查找，假设Path（AB）的值为P，那么接着查找Path（AP），假设Path（AP）的值为L，那么接着查找Path（AL），假设Path（AL）的值为A，则查找结束，最短路径为A->L->P->B。

那么，如何填充Path的值呢？很简单，当我们发现Dis（AX） + Dis（XB） < Dis（AB）成立时，就要把最短路径改为A->...->X->...->B，而此时，Path（XB）的值是已知的，所以，Path（AB） = Path（XB）。

下面的就是代码的具体实现了：

CreateGraphDemo.h#ifndef __CREATE_GRAPH_DEMO_H#define __CREATE_GRAPH_DEMO_H#include <stdio.h>#include <stdlib.h>#include <string.h>#ifndef false #define false 0#endif#ifndef true #define true 1#endif#ifndef error #define error -1#endif#define INFINITYINT_MAX#define MAX_VERTEX_NUM20#define MAX_INFO 100#define MAX_NAME 10typedef int VRType;typedef char InfoType;typedef char* VertexType;VRType visited[MAX_VERTEX_NUM];typedef enum{DG, DN, UDG, UDN} GraphKind;typedef struct ArcCell{VRTypeadj;//VRType是顶点关系类型，对无权图，用1或0表示相邻否，对带权图，则为权值类型InfoType *info;//该弧相关信息的指针}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexTypevexs[MAX_VERTEX_NUM]; // 顶点向量AdjMatrix arcs; // 邻接矩阵VRTypevexnum, arcnum; // 图的当前顶点数和弧数GraphKind kind; // 图的种类标志}MGraph;//栈的结构typedef struct{VRType *base;VRType *top;}SqStack;#ifdef __cplusplusextern "C"{#endif//返回指定顶点elem在顶点向量中的位置int LocateVex（MGraph G, VertexType elem）;//创建无向网int CreateUDN（MGraph *G）;//创建有向图int CreateDN（MGraph *G）;//显示其对应的邻接矩阵int Display（MGraph *G）;//显示景点int DisplayVexs（MGraph *G）;//释放空间int FreeGraph（MGraph **G）;//最短路径算法void FloydMethods（int Dis[][MAX_VERTEX_NUM], int Path[][MAX_VERTEX_NUM], int vexnum）;//输出最短路径以及路径长度void ShowShortPath（int Dis[][MAX_VERTEX_NUM], int Path[][MAX_VERTEX_NUM], SqStack *S, MGraph *G）;//初始化栈int InitStack（SqStack *S）;//压栈操作int Push（SqStack *S, int e）;//出栈操作int Pop（SqStack *S, int *e）;#ifdef _cplusplus}#endif#endif