【基礎知識】|?作者?/ Edison Zhou這是恰童鞋騷年的第223篇原創文章圖的最重要的應用之一就是在交通運輸和通信網絡中尋找最短路徑。例如在交通網絡中經常會遇到這樣的問題：兩地之間是否有公路可通；在有多條公路可通的情況下，哪一條路徑是最短的等等。這就是帶權圖中求最短路徑的問題，此時路徑的長度不再是路徑上邊的數目總和，而是路徑上的邊所帶權值的和。
帶權圖分為無向帶權圖和有向帶權圖，但如果從A地到B地有一條公路，A地和B地的海拔高度不同，由于上坡和下坡的車速不同，那么邊和邊上表示行駛時間的權值也不同。
考慮到交通網絡中的這種有向性，本篇也只討論有向帶權圖的最短路徑。一般習慣將路徑的開始頂點成為源點，路徑的最后一個頂點成為終點。
單源點最短路徑是指給定一個出發點(源點)和一個有向圖，求出源點到其他各頂點之間的最短路徑。對于下圖左邊所示的有向圖G，設頂點0為源點，則其到其他各頂點的最短路徑如下圖右邊所示。
從上圖中可以看出，從源點0到終點4一共有4條路徑：
(1)0→4 路徑長度：90
(2)0→3→4 ?路徑長度：90
(3)0→1→2→4 ?路徑長度：70
(4)0→3→2→4 ?路徑長度：60
可以看出，源點0到終點4的最短路徑為第(4)條路徑。
為了求出最短路徑，前人們已經做很多工作，為我們奉獻了兩個重要的算法：Dijkstra(迪杰斯特拉)和Floyd(弗洛伊德)算法，下一篇開始我們就來看看這兩個算法。
3小結本篇介紹了圖的一個重要應用場景—最短路徑及單源點最短路徑的概念，下一篇開始，我們開始學習Dijkstra算法和Floyd算法。
4參考資料程杰，《大話數據結構》陳廣，《數據結構(C#語言描述)》段恩澤，《數據結構(C#語言版)》往期精彩回顧每天5分鐘用C#學習數據結構(26)
如果本文對你有用，不妨點個“在看”或者轉發朋友圈
?點擊
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
