最短路徑
旅行家的困擾
第4章 圖結構 解放軍理工大學
旅行家的困擾
新
疆
特
克
斯
縣
“
八
卦
城
”
第4章 圖結構 解放軍理工大學
旅行家的困擾
特克斯縣
怎么樣幫
助困擾的旅行
家找到去各個
地點的最短路
線呢?
旅行家居住的旅館
旅行家想去的地點
第4章 圖結構 解放軍理工大學
問題建模
使用加權有向圖進行建模: 3 5 6 7 4 7 6 4
1 7 4
1、將特克斯縣中的道路交點 9 5 4 3 2 2 5 9
6 4
看作圖的頂點 7 3 2 2 3
2 2
2 、將城市中的道路看作