有向图的最短路径——Floyd算法（简单的计算机学习）

下面

假如小明暑假要去旅游，总共有四个城市，有些城市有到另外一个城市的高铁，有些城市则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。

图中共有四个城市和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');

}

}