Floyd最短路径算法.docx

精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载
Floyd最短路径算法
Floyd最短路径算法
2006-10-20, by leon_jlu 在图论中 经常会遇到这样的问题，在一个有向图 里，求出任意两个节点之间的最值是已知的，换句话说，就 是k->...->j这条路是已知的，所以 k->...->j这条路上j的上一个城市(即 p(kj))也是已知的，当然，因为要改走 i->...->k->...->j这一条路，j的上一个城 市正好是p(kj) o所以一旦发现
精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载
精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载
d(ij)>d(ik)+d(kj),就把 p(kj)存入 p(ij)。
下面是具体的 C代码： #include
#include #include #define
MAXSIZE 20 void
floyd(int [MAXSIZE], int [MAXSIZE],
int); void display_path(int
[MAXSIZE], int [MAXSIZE], int); void reverse(int , int); void
readin(int [MAXSIZE], int *); #define MAXSUM(a, b) (((a) != INT_MAX && (b) != INT_MAX) ?
((a) + (b)) : INT_MAX) void
floyd(int dist[MAXSIZE], int path[MAXSIZE], int n) { int i, j, k; for (i = 0; i MAXSUM(dist[k], dist[k][j])) { path[j] = path[k][j];
dist[j] = MAXSUM(dist[k], dist[k][j]); } } void
display_path(int dist[MAXSIZE], int path[MAXSIZE], int n) { int *chain; int count; int i, j, k; printf(\ Dist printf(
精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 ~ 5 ~
精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载
chain = (int *) malloc(sizeof(int)*n);
for (i = 0; i Dest Dist Path
1->2 5 1->2 1->3 15
1->2->4->3 1->4 10
1->2->4 2->1 20 2->4->1
2->3 10 2->4->3 2->4
5 2->4 3->1 30 3->1
3->2 35 3->1->2 3->4
15 3->4 4->1 15
4->1 4->2 20 4->1->2
4->3 5 4->3 Dijkstra 算法是荷
兰计算机科学家艾兹格 ？迪科斯彻发现 的。算法解决的是有向图中最短路径问 题。 举例来说，如果图中的顶点
表示城市，而边上的权重表示著城市间 开车行经的距离。 Dijkstra算法可以用
来找到两个城市之间的最短路径。
Dijkstra算法的输入包含了一个有权重 的有向图G,以及G中的一个来源顶点 So我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成 精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载 ~ 6 ~
================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============
的有序元素对。(u,v)表示从顶点u到v 有路径相连。 我们以E所有边的集合， 而边的权重则权重函数 w: E f [0, 定] 义。因此，w(u,v)就是从顶点u到顶点 v的非负花费值(cost)o边的花费可以想 像成两个顶点之间的距离。任两点间路 径的花费值，就是该路径上所有边的花 费值总和。 已知有V中有顶点s及t,
Dijkstra算法可以找到s到t的最低花费 路径(最短路径)。这个算法也可以在一 个图中，找到从一个顶点 s到任何其他 顶点的最短路径。 算法描述
这个算法是通过为每个顶点 v保留目前
为止所找到的从s到v的最短路径来工 作的。初始时，源点s的路径长度值被 赋为0,同时把所有其他顶点的路径长 度设为无穷大，即表示我们不知道任何 通向这些顶点的路径。当算法结束时， d[v]中储存的便是从s到v的最短路径， 或者如果路径不存在的话是无穷大。
Dijstra算法