如圖所示,從甲地到乙地有兩條路線,哪條路線短?為什麽?如下：
甲→乙→丁的走法為2×2=4種；甲→丙→丁的走法為1×3=3種，***有4+3=7種。解：2×2=4；1×3=3；4+3=7，從甲地到丁地***有7種不同走法。
最短路線問題是圖論研究中的壹個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。最短路徑問題是圖論研究中的壹個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：
1、確定起點的最短路徑問題-即已知起始結點，求最短路徑的問題。適合使用Dijkstra算法。
2、確定終點的最短路徑問題-與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
3、確定起點終點的最短路徑問題-即已知起點和終點，求兩結點之間的最短路徑。全局最短路徑問題-求圖中所有的最短路徑。適合使用Floyd-Warshall算法。
這個算法是通過為每個頂點v保留所找到的從s到v的最短路徑來工作的。初始時，原點s的路徑權重被賦為0（d[s]=0）。若對於頂點s存在能直接到達的邊（s,m），則把d[m]設為w（s,m）。
同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於所有頂點的集合V中的任意頂點v，若v不為s和上述m之壹，d[v]=∞）。當算法結束時，d[v]中存儲的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。
邊的拓展是Dijkstra算法的基礎操作：如果存在壹條從u到v的邊，那麽從s到v的最短路徑可以通過將邊（u,v）添加到尾部來拓展壹條從s到v的路徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。