数据结构：最短路径算法.pptVIP

图算法（二） 最短路经 Shortest Path Dijkstra算法练习题链接 /vjudge/contest/view.action?cid=29337#overview Floyd算法练习题链接 /vjudge/contest/view.action?cid=29305#overview 密码都是：671 /sjjg/DataStructure/DS/web/flashhtml/Dijkstra.htm 这个链接是Dijskra算法的动态演示 最短路径问题 最短路径问题 单源最短路径 Single-Source Shortest Path (Dijkstra算法) 单源最短路径 Single-Source Shortest Path 问题: 带权有向图G（E,V), 找出从给定源顶点s到其它顶点v的权最小路径。 “最短路径” = 最小权 路径的权是路径上所有边的权之和。 例：道路图 : 从青岛理工到金沙滩的最短路径? 单源最短路径 图中从v0到其余各顶点之间的最短路径: v0到 v1 无 v0到 v2 (v0 ,v2 ) 10 v0到 v3 (v0 ,v4 , v3) 50 v0到 v4 (v0 ,v4) 30 v0到 v5 (v0 ,v4 , v3 ,v5) 60 权非负的单源最短路径算法（Dijkstra） 贪心算法： 若顶点序列{V0,V1,…,Vn} 是从V0到Vn的最短路，则序列 {V0,V1,…,Vn-1} 必为从V0到Vn-1的最短路。 权非负的单源最短路径算法（Dijkstra） 基本思想： 将图中所有顶点分成两组:S, V-S 一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。 S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。 权非负的单源最短路径算法（Dijkstra） 初始时,S仅包含源v0, 特殊路径： 从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。 步骤: (1) 取v0加入S中 (2) 从V-S中取出具有当前最短路径长度的顶点w加入S中。 权非负的单源最短路径算法（Dijkstra） 权非负的单源最短路径算法（Dijkstra） void init() // 对一些数据进行初始化 {int i , j; for(i = 1; i = n; i++) for(j = 1; j = n; j++) grap[i][j] = INF; memset(pre , 0 , sizeof(pre)); } void dijkstra(int u) { int i , j; for(i = 1; i = n; i++) //首先求出源点到其他所有点的距离 dist[i] = grap[u][i]; pre[u] = 1; int x = u; for(i = 1; i n-1; i++) {int maxs = INF; for(j = 1; j = n; j++) // 类似于最小生成树prim算法 ， 找到距离最短的那个点 if(!pre[j] maxs dist[j]) { maxs = dist[j]; x = j; } pre[x] = 1; for(j = 1; j = n; j++) //然后再通过这个点去得到其他点的最短距离 if(!pre[j] dist[j] (dist[x]+grap[x][j]) grap[x][j] INF) dist[j] = grap[x][j] + dist[x]; } } int main() { scanf(%d %d , n , m); init(); int i , x , y , z; for(i = 0; i m; i++) //对有向图进行存储 { scanf(%d %d %d , x , y , z); grap[x][y] = z; } dijkstra(1); //假设求点1到其他点的最短路 return 0; } 所有顶点对之间的最短路径算法Floyd算法 已知一个有向图（无向图），对于每对顶点Vi ！=Vj ，求出它们之间的最短路径长度。 解决这个问题有两种方法： （1）轮流以