用c语言实现寻找最短距离的问题,照片是个例子,问题就是从x城市到y城市...

发布网友发布时间：2024-10-06 02:18

共1个回答

热心网友时间：2024-10-08 12:03

　　单源最短路径问题，用Dijkstra算法求解。图的存储结构，有邻接矩阵和邻接表两种，邻接矩阵占用空间大，但是使用方便。这里就说一下邻接矩阵：

struct Graph{
int matrix[N][N];
int e;
};

　　N表示顶点数，就这幅图而言是5，e表示边数。matrix存储了顶点之间的距离，比如matrix[0][1]表示顶点0到顶点1之间的距离。matrix[n][n]表示一个顶点到它自己的距离，这个应当设为0。另外，若两个顶点之间没有边，应该用一个值（可以是负数）来标识它，这两项操作，应该在图的初始化时进行。

　　创建图之后，首先要输入边数，然后输入每条边的起点、终点和长度，来给数组matrix赋值。

　　然后就是使用算法了。

　　参考：http://www.cnblogs.com/dolphin0520/archive/2011/08/26/2155202.html