数据结构最短路径

一个图的存储矩阵如下所示（顶点分别是0、1、2、3、4、5）：

0， 12， 18， ∞， 17， ∞

12, 0， 10， 3， ∞， 5 18，10， 0， ∞， 21， 11 ∞， 3， ∞， 0， ∞， 8 17， ∞， 21， ∞， 0， 16 ∞， 5， 11， 8， 16， 0

试用邻接矩阵存储法和Floyd算法求解任意两个顶点的最短路径。 输入：

输入数据第一行为1个正整：顶点个数n(顶点将分别按0，1，…，n-1进行编号)。后面有n+1行，前n行都有n个整数（第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边）；第n+1行输入一对顶点x和y

输出：

x和y顶点的最短路径长度和最短路径(路径换行输出，只输出顶点编号序列)。

问题分析

题目要求图的存储类型为邻接矩阵，这种存储结构简单易懂，但存储占用较大；求最短路径的算法有Dijkstra算法和SPFA算法，三者相比，在代码的实现上，Floyd编写简单且容易理解，缺点是时间复杂度较高，不适合计算大量的数据。

数据结构及程序

#include #define inf 10000 #define maxn 11

int N,g[maxn][maxn]={0}; int path[maxn][maxn]={0};

void floyd() { for(int k=0;kfor(int i=0;i(g[i][k]+g[k][j])) { g[i][j]=g[i][k]+g[k][j]; path[i][j]=k; } } }

int main() { scanf(\"%d\ for(int i=0;i\ while(tmp!=y) { printf(\"%d->\ tmp=path[tmp][y]; } printf(\"%d\\n\}

运行结果

实验结论

基本Floyd算法就是三次循环，很容易就可以写出，但是在输出路径时可能会有一些小问题。首先需要在Floyd函数中开辟path数组存储路径，在输出时，需要回溯path数组才能输出路径节点。