dijkstra算法floyd算法.ppt

Dijkstra算法 Floyd算法五、图的应用求有向网中顶点间的最短路径求有向无环网(AOE)的关键路径对有向无环图(AOV)进行拓扑排序Prim算法 Kruskal算法求无向网的最小生成树1【问题】设下图中各顶点代表城市,边代表城市间可能设置的通信线路,边上的权值为该线路的造价。如何建立通信网络,才能使总造价最低?1、最小生成树bcaed36565f52641【分析】 n个城市间只需建立n-1条通信线路即可相互通信,要使总造价最低,只需所选各边权值之和最小,即求连通的无向网的最小生成树。2⑶重复⑵直至U=V,则N’=(V,{TE})即为所求最小生成树。1、最小生成树⑵令F={(v1,v2)|(v1,v2)∈E,v1∈U,v2∈V-U},在F中找一条权值最小的边(u,v)加入TE,并将v加入U;⑴任选顶点u0∈V,令U={u0},TE={};设无向网N=(V,{E})连通,∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uabcdef00000056∞∞∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uabcdef00000056∞∞∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uadef00000056∞∞∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uadef00000056∞∞∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uadef00200055∞∞∞1∞∞65551∞∞∞554∞3∞652∞∞44∞36∞∞65∞∞426∞-Uadef00200055∞∞0adjcostclosedge213045bc10