(7.8.1)--ch7-12-图的单源最短路径-Dijkstra思想.pdf
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 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 between 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 source 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 characteristic 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 directly 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 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 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 and 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！
