【問題概述】最短路徑問題是圖論研究中的一個經典算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑．算法具體的形式包括：
①確定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題．
②確定終點的最短路徑問題 - 與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題．
③確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑．
④全局最短路徑問題 - 求圖中所有的最短路徑．
【問題原型】“將軍飲馬”，“造橋選址”，“費馬點”．
【涉及知識】“兩點之間線段最短”，“垂線段最短”，“三角形三邊關係”，“軸對稱”，“平移”．
【出題背景】角、三角形、菱形、矩形、正方形、梯形、圓、座標軸、拋物線等．
【解題思路】找對稱點實現“折”轉“直”，近兩年出現“三折線”轉“直”等變式問題考查．
【十二個基本問題】
分享到:
閱讀更多 雪落無聲80945706 的文章
