首页 > 代码库 > “Chaos”的算法之Floyd算法
“Chaos”的算法之Floyd算法
求最短路径的经典方法有很多种,最常用的便是迪杰斯特拉算法和佛洛依德(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的最短路径的距离。
直接上代码:
1 /* 求各个顶点对之间的最短路径 */ 2 for (int k = 0; k < G.vtxCnt; ++k) { // 顶点循环 3 for (int i = 0; i < G.vtxCnt; ++i) { // 起点循环 4 for (int j = 0; j < G.vtxCnt; ++j) { // 终点循环 5 // 判断是否存在更短的路径,有,则边值矩阵和路径矩阵更新;dist[in][post]得出的是in到post的最短路径 6 if (dist[i][j] > dist[i][k] + dist[k][j]) { 7 dist[i][j] > dist[i][k] + dist[k][j]; 8 path[i][j] = path[k][j]; 9 }10 }11 }12 }
那么接下来的问题就是,我们如何找出最短路径呢?这里需要借助一个辅助数组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)。
下面的就是代码的具体实现了:
1 CreateGraphDemo.h 2 #ifndef __CREATE_GRAPH_DEMO_H 3 #define __CREATE_GRAPH_DEMO_H 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 #ifndef false 8 #define false 0 9 #endif 10 #ifndef true 11 #define true 1 12 #endif 13 #ifndef error 14 #define error -1 15 #endif 16 #define INFINITY INT_MAX 17 #define MAX_VERTEX_NUM 20 18 #define MAX_INFO 100 19 #define MAX_NAME 10 20 typedefint VRType;21 typedefchar InfoType;22 typedefchar* VertexType;23 VRType visited[MAX_VERTEX_NUM];24 typedefenum{ DG, DN, UDG, UDN } GraphKind;25 typedefstruct ArcCell26 {27 VRType adj;//VRType是顶点关系类型,对无权图,用1或0表示相邻否,对带权图,则为权值类型 28 InfoType *info;//该弧相关信息的指针 29 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];30 typedefstruct31 {32 VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 33 AdjMatrix arcs; // 邻接矩阵 34 VRType vexnum, arcnum; // 图的当前顶点数和弧数 35 GraphKind kind; // 图的种类标志 36 }MGraph;37 //栈的结构 38 typedefstruct39 {40 VRType *base;41 VRType *top;42 }SqStack;43 #ifdef __cplusplus 44 extern"C"{45 #endif 46 //返回指定顶点elem在顶点向量中的位置 47 int LocateVex(MGraph G, VertexType elem);48 //创建无向网 49 int CreateUDN(MGraph *G);50 //创建有向图 51 int CreateDN(MGraph *G);52 //显示其对应的邻接矩阵 53 int Display(MGraph *G);54 //显示景点 55 int DisplayVexs(MGraph *G);56 //释放空间 57 int FreeGraph(MGraph **G);58 //最短路径算法 59 void FloydMethods(int Dis [][MAX_VERTEX_NUM], int Path [][MAX_VERTEX_NUM], int vexnum);60 //输出最短路径以及路径长度 61 void ShowShortPath(int Dis [][MAX_VERTEX_NUM], int Path [][MAX_VERTEX_NUM], SqStack *S, MGraph *G);62 //初始化栈 63 int InitStack(SqStack *S);64 //压栈操作 65 int Push(SqStack *S, int e);66 //出栈操作 67 int Pop(SqStack *S, int *e);68 #ifdef _cplusplus 69 }70 #endif 71 #endif
1 //CreateGraphDemo.c 2 #include "CreateGraphDemo.h" 3 int visited[20]; 4 //返回指定顶点在顶点向量中的位置 5 int LocateVex(MGraph G, VertexType elem) 6 { 7 int i; 8 for (i = 0; i < G.vexnum; ++i) 9 if (strcmp(elem, G.vexs[i]) == 0) 10 return i; 11 return error; 12 } 13 void FloydMethods(int Dis [][MAX_VERTEX_NUM], int Path [][MAX_VERTEX_NUM], int _nVertexCount) 14 { 15 int i, j, k; 16 // 先初始化Path 17 for (i = 0; i < _nVertexCount; ++i) 18 { 19 for (j = 0; j < _nVertexCount; ++j) 20 { 21 Path[i][j] = i; 22 } 23 } 24 for (k = 0; k < _nVertexCount; ++k) 25 { 26 for (i = 0; i < _nVertexCount; ++i) 27 { 28 for (j = 0; j < _nVertexCount; ++j) 29 { 30 if ((Dis[i][k] + Dis[k][j]) < Dis[i][j]) 31 { 32 // 找到更短路径 33 Dis[i][j] = Dis[i][k] + Dis[k][j]; 34 Path[i][j] = Path[k][j]; 35 } 36 } 37 } 38 } 39 } 40 void ShowShortPath(int Dis [][MAX_VERTEX_NUM], int Path [][MAX_VERTEX_NUM], SqStack *S, MGraph *G) 41 { 42 int i, j, e, t, m, len = 0; 43 char Name1[10], Name2[10]; 44 printf("\n请输入你想查找的两个景点名称 (两景点间用空格隔开) : "); 45 scanf("%s %s", Name1, Name2); 46 printf("起源 -> 目的地 最小距离 最短路径\n"); 47 for (i = 0; i < G->vexnum; ++i) 48 { 49 for (j = 0; j < G->vexnum; ++j) 50 { 51 if (!strcmp(Name1, (*G).vexs[i]) && !strcmp(Name2, (*G).vexs[j])) 52 { 53 printf("%s -> %s\t", (*G).vexs[i], (*G).vexs[j]); 54 if (1000 == Dis[i][j]) // i -> j 不存在路径 55 { 56 printf("%s-->>%s is no road\n", (*G).vexs[i], (*G).vexs[j]);; 57 } 58 else 59 { 60 printf(" %d\t\t", Dis[i][j]); 61 int k = j; 62 do 63 { 64 k = Path[i][k]; 65 Push(S, k); 66 len++; 67 } while (k != i); 68 Pop(S, &e); 69 printf("%s", (*G).vexs[e]); 70 t = e; 71 for (m = 0; m < len; m++) 72 { 73 Pop(S, &e); 74 if (t != e) 75 { 76 printf(" -> %s", (*G).vexs[e]); 77 } 78 t = e; 79 } 80 printf(" -> %s\n", (*G).vexs[j]); 81 } 82 } 83 } 84 } 85 } 86 int InitStack(SqStack *S) 87 { 88 S->base = (int *) malloc(50 * sizeof(int)); 89 if (!S->base) 90 return error; 91 S->top = S->base; 92 returntrue; 93 } 94 int Push(SqStack *S, int e) 95 { 96 *(S->top++) = e; 97 returntrue; 98 } 99 int Pop(SqStack *S, int *e)100 {101 if (S->top == S->base)102 returnfalse;103 *e = *(--(S->top));104 returntrue;105 }106 //无向网 107 int CreateUDN(MGraph *G)108 {109 int i, j, k, l, IncInfo, w;//IncInfo表示弧是否有其他信息 110 char s[MAX_INFO], *info;111 char va[10], vb[10];112 printf("请输入校园中的景点个数,所有景点之间的马路条数,景点是否含有其他信息(是:1,否:0)");113 scanf("%d,%d,%d", &(*G).vexnum, &(*G).arcnum, &IncInfo);114 printf("请输入每个景点的名称(<%d个字符):\n", MAX_NAME);115 for (i = 0; i < (*G).vexnum; ++i)//构造顶点向量 116 {117 (*G).vexs[i] = (VertexType) malloc(sizeof(char) *MAX_NAME);118 scanf("%s", (*G).vexs[i]);119 getchar();120 }121 for (i = 0; i < (*G).vexnum; ++i)//初始化邻接矩阵 122 {123 for (j = 0; j < (*G).vexnum; ++j)124 {125 (*G).arcs[i][j].adj = 1000;126 (*G).arcs[i][j].info = NULL;127 }128 }129 printf("请输入%d条路中每条路所连接的两个景点(以空格隔开): \n", (*G).arcnum);130 for (k = 0; k < (*G).arcnum; ++k)131 {132 scanf("%s %s", va, vb);//输入弧头,弧尾信息 133 printf("请输入该条路的长度 : ");134 scanf("%d", &w);135 i = LocateVex(*G, va);//定位弧尾位置, 136 j = LocateVex(*G, vb);//定位弧头位置 137 (*G).arcs[i][j].adj = w;//权值大小 138 (*G).arcs[j][i].adj = w;139 if (IncInfo)140 {141 printf("请输入该景点的相关信息(<%d个字符) : ", MAX_INFO);142 scanf("%s", s);143 l = strlen(s);144 if (l)145 {146 (*G).arcs[i][j].info = (char *) malloc((l + 1)*sizeof(char));147 strcpy((*G).arcs[i][j].info, s);148 }149 }150 }151 (*G).kind = DN;152 returntrue;153 }154 //有向网 155 int CreateDN(MGraph *G)156 {157 int i, j, k, l, IncInfo, w;//IncInfo表示弧是否有其他信息 158 char s[MAX_INFO], *info;159 char va[5], vb[5];160 printf("请输入校园中的景点个数,所有景点之间的马路条数,景点是否含有其他信息(是:1,否:0)");161 scanf("%d,%d,%d", &(*G).vexnum, &(*G).arcnum, &IncInfo);162 printf("请输入每个景点的名称(<%d个字符)\n", MAX_NAME);163 for (i = 0; i < (*G).vexnum; ++i)//构造顶点向量 164 {165 (*G).vexs[i] = (VertexType) malloc(sizeof(char) * 5);166 scanf("%s", (*G).vexs[i]);167 getchar();168 }169 for (i = 0; i < (*G).vexnum; ++i)//初始化邻接矩阵 170 for (j = 0; j < (*G).vexnum; ++j)171 {172 (*G).arcs[i][j].adj = 1000;173 (*G).arcs[i][j].info = NULL;174 }175 printf("请输入%d条路中每条路所连接的两个景点(以空格隔开): \n", (*G).arcnum);176 for (k = 0; k < (*G).arcnum; ++k)177 {178 scanf("%s %s", va, vb);//输入弧头,弧尾信息 179 printf("请输入该条路的长度 : ");180 scanf("%d", &w);181 i = LocateVex(*G, va);//定位弧尾位置, 182 j = LocateVex(*G, vb);//定位弧头位置 183 (*G).arcs[i][j].adj = w;//权值大小 184 if (IncInfo)185 {186 printf("请输入该景点的相关信息(<%d个字符) : ", MAX_INFO);187 scanf("%s", s);188 l = strlen(s);189 if (l)190 {191 (*G).arcs[i][j].info = (char *) malloc((l + 1)*sizeof(char));192 strcpy((*G).arcs[i][j].info, s);193 }194 }195 }196 (*G).kind = DN;197 returntrue;198 }199 int Display(MGraph *G)200 {201 int i, j;202 printf("邻接矩阵输出 :\n");203 for (i = 0; i < G->vexnum; i++)204 {205 for (j = 0; j < G->vexnum; j++)206 {207 printf("%d ", G->arcs[i][j].adj);208 }209 printf("\n");210 }211 }212 int DisplayVexs(MGraph *G)213 {214 int i;215 printf("---------------------景点:--------------------\n");216 for (i = 0; i < G->vexnum; ++i)217 {218 printf("%s ", G->vexs[i]);219 }220 printf("\n------------------------------------------------\n\n");221 }222 int FreeGraph(MGraph **G)223 {224 int i, j;225 for (i = 0; i < (*(*G)).vexnum; i++)226 {227 free((*G)->vexs[i]);228 (*G)->vexs[i] = NULL;229 for (j = 0; j < (*(*G)).vexnum; j++)230 {231 if ((*G)->arcs[i][j].info)232 {233 free((*G)->arcs[i][j].info);234 (*G)->arcs[i][j].info = NULL;235 }236 }237 }238 free(*G);239 *G = NULL;240 returntrue;241 }
1 //main.c 2 #include "CreateGraphDemo.h" 3 int main(int argc, char *argv []) 4 { 5 int i, j, a[20][20], b[20][20]; 6 char ch; 7 SqStack S; 8 MGraph **p, *G = (MGraph *) malloc(sizeof(MGraph)); 9 p = &G;10 CreateUDN(G);11 //CreateDN(G); 12 for (i = 0; i < G->vexnum; ++i)13 {14 for (j = 0; j < G->vexnum; ++j)15 {16 a[i][j] = G->arcs[i][j].adj;17 }18 }19 InitStack(&S);20 FloydMethods(a, b, G->vexnum);21 loop:22 DisplayVexs(G);23 ShowShortPath(a, b, &S, G);24 printf("Again ? (Y/N)\n");25 getchar();26 scanf("%c", &ch);27 if (‘y‘ == ch || ‘Y‘ == ch)28 goto loop;29 FreeGraph(p);30 return 0;31 }
这是我之前写的一个校园导航的Demo,希望对大家有用……
本文出自 “驿落黄昏” 博客,请务必保留此出处http://yiluohuanghun.blog.51cto.com/3407300/879900