“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. for(k = 0; k < Number; ++k)  

2.    {  

3. for(i = 0; i < Number; ++i)  

4.        {  

5. for(j = 0; j < Number; ++j)  

6.            {  

7. if((Dis[i][k] + Dis[k][j]) < Dis[i][j])  

8.                {  

9. // 找到更短路径  

10.                    Dis[i][j] = Dis[i][k] + Dis[k][j];  

11.                }  

12.            }  

13.        }  

14. }

那么接下来的问题就是，我们如何找出最短路径呢？这里需要借助一个辅助数组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 ArcCell  

26. {  

27.    VRType  adj;//VRType是顶点关系类型，对无权图，用1或0表示相邻否，对带权图，则为权值类型

28.    InfoType *info;//该弧相关信息的指针

29. }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  

30. typedefstruct

31. {  

32.    VertexType  vexs[MAX_VERTEX_NUM];       // 顶点向量

33.    AdjMatrix   arcs;                       // 邻接矩阵

34.    VRType      vexnum, arcnum;             // 图的当前顶点数和弧数

35.    GraphKind   kind;                       // 图的种类标志

36. }MGraph;  

37. //栈的结构

38. typedefstruct

39. {  

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. }