下面
假如小明暑假要去旅游,总共有四个城市,有些城市有到另外一个城市的高铁,有些城市则没有,如下图。为了节省经费以及方便计划旅程,小哼希望在出发之前知道任意两个城市之前的最短路程。
图中共有四个城市和8条高铁路线,在图论中我们习惯用点表示城市(字母V),用有向边表示高铁路线(字母E),路程称为这两点间有向线的权值,现在我们需要一个矩阵来存储数据,对此我们可以作出该二维矩阵图
城市一到城市一距离为0,所以同理对角线上所有权值都为0,无穷大表示该城市到另外一个城市并没有开通高铁,现在我们就要开始求最短的路径了。
因为我们的矩阵已经记录了Vi到Vj的两个城市之间的每一个权值,接下来我们只需要找到(V1到Vk) (Vk到Vj)的权值与Vi到Vj的进行比较,通过这个顶点k中转即i->k->j,缩短了原来从顶点i点到顶点j的路程,甚至有时候不只通过一个点,而是经过两个点或者更多点中转会更短,我们通过k的每一次改变都能判断以k为中心点的三点之间最短路程。
c语言代码如下
/*
* floyd最短路径。
* 即,统计图中各个顶点间的最短路径。
*
* 参数说明:
* G -- 图
* path -- 路径。path[i][j]=k表示,'顶点i'到'顶点j'的最短路径会经过顶点k。
* dist -- 长度数组。即,dist[i][j]=sum表示,'顶点i'到'顶点j'的最短路径的长度是sum。
*/
void floyd(Graph G, int path[][MAX], int dist[][MAX])
{
int i,j,k;
int tmp;
// 初始化
for (i = 0; i < G.vexnum; i )
{
for (j = 0; j < G.vexnum; j )
{
dist[i][j] = G.matrix[i][j]; // '顶点i'到'顶点j'的路径长度为'i到j的权值'。
path[i][j] = j; // '顶点i'到'顶点j'的最短路径是经过顶点j。
}
}
// 计算最短路径
for (k = 0; k < G.vexnum; k )
{
for (i = 0; i < G.vexnum; i )
{
for (j = 0; j < G.vexnum; j )
{
// 如果经过下标为k顶点路径比原两点间路径更短,则更新dist[i][j]和path[i][j]
tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] dist[k][j]);
if (dist[i][j] > tmp)
{
// 'i到j最短路径'对应的值设,为更小的一个(即经过k)
dist[i][j] = tmp;
// 'i到j最短路径'对应的路径,经过k
path[i][j] = path[i][k];
}
}
}
}
// 打印floyd最短路径的结果
printf('floyd: \n');
for (i = 0; i < G.vexnum; i )
{
for (j = 0; j < G.vexnum; j )
printf('%2d ', dist[i][j]);
printf('\n');
}
}
联系客服