搜索
最短路问题最短路问题的研究在现实生活中有哪些应用？•管道的铺设•线路的安排•厂区的布局•设备的更新v1v2v3v4v5v6v7v8v9632211610410322463问题：求网络中起点到其它点的一条最短路线引例：求网络中V1－V9的最短路•算法：Dijkstra(狄克斯特拉)标号法•基本思想：从起点Vs开始，逐步给每个节点V标号［dj,vi］，其中dj是起点Vs到vj的最短距离，vi为该最短路线上的前一节点。算法：Dijkstra(狄克斯特拉)标号法Step1:给起点v1标号［0，v1］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］算法：Dijkstra(狄克斯特拉)标号法Step2:把顶点v分成VA:已标号点集VB:未标号点集v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］算法：Dijkstra(狄克斯特拉)标号法Step3:考虑所有这样的边（vi,vj）其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号。v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］算法：Dijkstra(狄克斯特拉)标号法Step3:考虑所以这样的边（vi,vj）其中vi∈VA，vj∈VB，挑选其中与起点v1距离最短（min{di+cij}）的vj，对vj进行标号。v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］算法：Dijkstra(狄克斯特拉)标号法Step4:重复2，3步骤，直至终点vn标上［dn,vi］,着dn即为v1－vn的最短距离，反向追踪可找出最短路。v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［0,v1］v1v2v3v4v5v6v7v8v9632211610410322463［1,v1］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］［10,v5］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］［10,v5］v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］［10,v5］［12,v5］此时，终点标号为［12,v5］,即v1—vn的最短距离为12，反向追踪可求出最短路。v1v2v3v4v5v6v7v8v9632211610410322463［0,v1］［1,v1］［3,v1］［5,v3］［6,v2］［9,v5］［10,v5］［12,v5］v1－v9的最短路为：v1-v3-v2-v5-v9,最短距离为12•Dijkstra算法的补充说明①标号过程中间结点的标号内容有明确的意义②同一问题可能存在多个最短路，但距离是唯一的③当网络中出现负的权数时，算法失效。v1v2v31-32[0,v1][1,v1]•Dijkstra算法的补充说明①标号过程中间结点的标号内容有明确的意义②同一问题可能存在多个最短路，但距离是唯一的③当网络中出现负的权数时，算法失效。④前面的算法描述针对有向网络图，但对于无向的网络图，只需将step3中的（vi,vj）改为［vi,vj］，算法同样适用。Thankyou