(7.8.1)--ch7-12-图的单源最短路径-Dijkstra思想.pdf

《(7.8.1)--ch7-12-图的单源最短路径-Dijkstra思想.pdf》由会员分享，可在线阅读，更多相关《(7.8.1)--ch7-12-图的单源最短路径-Dijkstra思想.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Data Structures and Algorithms Single Source Shortest Path of Graphs Dijkstra IdeaData Structures and AlgorithmsData Structures and Algorithms1Chapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures and Algorithms2the shortest path problem of the weighted graphs In the

2、path from one vertex(source point)to another vertex(destination point),The path with the smallest sum of the weights of each side(or arc)is called the shortest path.the shortest path from one single source vertex to other vertexes in the graph Dijkstra algorithm(Dijkstra).the shortest path problem b

3、etween each pair of vertexes Floyd algorithm(Floyd)Chapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures and Algorithms*Dijkstra algorithm(Dijkstra)basic thought:Each path is calculated in order of increasing length of the shortest path。V0vivjThe shortest path form sou

4、rce point v0 to the vertex vi is the shortest length in the set of path lengths from the source point v0 to the points.the shortest path problem of the weighted graphsChapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures and Algorithms*Dijkstra algorithm(Dijkstra)The c

5、haracteristic of shortest path with shortest path length:On this path.It must contain only one arc and the weight of this arc should be the smallest.(Lets say v0 vi)The characteristic of shortest paths with the shortest length of the next path:There are only two possibilities:Or you could go directl

6、y from the source to the point vi which is just one arc.Or the vertex vk of the shortest path from the sourceChapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures and Algorithms*The characteristic of the rest of the shortest path:The characteristic of the next path,the

7、 shortest path with the shortest length:could be one of two things:Or you could just go from the source point to the point with just one arc.Or you can go from the source to the vertex vk,vi to the vertex.There is only one arc directly from the source to the point.Or the vertex in the shortest path

8、from the source And then you go to that vertex数数 据据 结结 构构Dijkstra algorithm(Dijkstra)Chapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures and Algorithms*Dijkstra algorithm(Dijkstra)Chapter7 Graphs7.5 Application of graphData Structures and AlgorithmsData Structures an

9、d Algorithms*v5v2v41003060101055020v3v1v0destination distV1V2V3V4V512345/60(V0,V4,V3,V5)/90(V0,V4,V5)/50(V0,V4,V3)/100(V0,V5)30(V0,V4)60(V0,V2,V3)/100(V0,V5)30(V0,V4)10(V0,V2)the shortest path lengh （v0,v2）10v5v2v4301020v3v1v010（v0,v4）30（v0,v4,v3）50（v0,v4,v3,v5)60 v0v1 无无D Da at ta a S St tr ru uc ct tu ur re es s a an nd d A Al lg go or ri it th hm ms s Thanks！