第6章图与网络分析 A 5 S B 米 D × C ×(E 4 最小部分树长Lmm=14 2021/2/21
2021/2/21 --第6章 图与网络分析-- --12-- S A B C D E T 5 4 5 5 × × × 最小部分树长Lmin=14
第6章图与网络分析 §63最短路问题 1.求某两点间最短距离的D( Dijkstra)氏标号法 在图示的网络图中,从给定的点S出发,要到达目 的地T。问:选择怎样的行走路线,可使总行程最短? 方法: Dijkstra(D氏)标号法—按离出发点的距离由 近至远逐渐标出最短距离和最佳行进路线 4 2021/2/21
2021/2/21 --第6章 图与网络分析-- --13-- §6.3 最短路问题 在图示的网络图中，从给定的点S出发，要到达目 的地T。问：选择怎样的行走路线，可使总行程最短？ 方法：Dijkstra（D氏）标号法——按离出发点的距离由 近至远逐渐标出最短距离和最佳行进路线。 S 1．求某两点间最短距离的D（Dijkstra）氏标号法 2 4 7
第6章图与网络分析 A 0 5 4 5 5 S B C E 4 最短路线:S→≯A→>B>E→D→T 2021/2/2 最短距离:Lmim=13 --14-
2021/2/21 --第6章 图与网络分析-- --14-- S A B C D E T 5 4 5 5 0 2 4 4 7 8 9 14 5 13 4 最短路线：S → A→B → E → D → T 最短距离：Lmin=13