最短路径问题(Dijkstra算法)和最小生成树(Kruskal算法和Prim算法).doc

上机实验12 最短路径问题Dijkstra算法 最小生成树Kruskal算法和Prim算法 一最短路径问题Dijkstra算法 实验问题描述如图的交通网络每条弧上的数字代表车辆在该路段行驶所需的时间有向边表示单行道无向边表示可双向行驶若有一批货物要从1号顶点运往11号顶点问运货车应沿哪条线路行驶才能最快地到达目的地 Dijkstra算法原理 设P(u,v)是加权图G中从u到v的路径,则该路径上的