尋路是指通過計算機應用程序繪制兩點之間最短的路線。它是解決迷宮問題的一個更實用的變體。這一領域的研究在很大程度上是基于Dijkstra在加權圖上尋找最短路徑的算法。尋路與圖論中的最短路徑問題密切相關，后者研究如何在一個大網絡中的兩點之間找出最符合某些標準（最短、最便宜、最快等）的路徑。

尋路方法的核心是通過從一個頂點開始，探索相鄰的節點，直到到達目的節點，通常是為了找到最便宜的路線。雖然像廣度優先搜索這樣的圖形搜索方法在有足夠時間的情況下會找到一條路線，但其他探索圖形的方法會傾向于更快地到達目的地。一個比喻是一個人走過一個房間；而不是事先檢查每一條可能的路線，這個人一般會沿著目的地的方向走，只有在避開障礙物時才會偏離路徑，并且使偏離盡可能小。尋路的兩個主要問題是：（1）尋找圖中兩個節點之間的路徑；以及（2）最短路徑問題--尋找最佳最短路徑。廣度優先和深度優先搜索等基本算法通過窮盡所有可能性來解決xxx個問題；從給定的節點開始，它們遍歷所有潛在的路徑，直到到達目標節點。這些算法的運行速度為{displaystyleO(|V|+|E|)}，或線性時間，其中V是頂點數量，E是頂點之間的邊數。或線性時間，其中V是頂點的數量，E是頂點之間的邊的數量。更復雜的問題是尋找最優路徑。這種情況下的窮舉法被稱為Bellman-Ford算法，它的時間復雜度為，或二次方時間。然而，沒有必要檢查所有可能的路徑來找到最優路徑。A*和Dijkstra算法等算法通過啟發式方法或動態編程，戰略性地消除路徑。通過消除不可能的路徑，這些算法的時間復雜度可以低至上述算法是xxx的一般算法之一，它們在圖上操作時無需預處理。然而，在實際的旅行路線系統中，通過對圖進行預處理以達到更好的性能的算法可以達到更好的時間復雜度。這樣的算法之一是收縮層次結構。

基于圖的尋路算法的一個常見例子是Dijkstra算法。這個算法從一個起始節點和一個開放的候選節點集開始。在每個步驟中，開放集中與起點距離最小的節點被檢查。該節點被標記為關閉，與之相鄰的所有節點如果尚未被檢查，則被添加到開放集。這個過程重復進行，直到找到通往目的地的路徑。由于最低距離的節點首先被檢查，所以xxx次發現目的地時，通向它的路徑將是最短的路徑。如果有一個負的邊緣權重，Dijkstra的算法就會失敗。在假設的情況下，節點A、B、C組成一個連接的無向圖，邊AB=3，AC=4，BC=-2，從A到C的最優路徑花費1，從A到B的最優路徑花費2。Dijkstra算法從A開始將首先檢查B，因為它是最近的。它將給它分配一個3的成本，并將其標記為關閉，這意味著它的成本將永遠不會被重新評估。因此，Dijkstra的方法不能評估負的邊權重。然而，由于在許多實際應用中，永遠不會出現負的邊權重，Dijkstra的算法在很大程度上適合尋路的目的。

A*算法A*是Dijkstra算法的一個變種，常用于游戲中。A*給每個開放節點分配一個權重，等于通往該節點的邊的權重加上該節點與終點之間的近似距離。這個近似距離是由啟發式算法找到的，代表了該節點與終點之間的最小可能距離。這使得它能夠在找到初始路徑后消除更長的路徑。如果在起點和終點之間有一條長度為x的路徑，而一個節點和終點之間的最小距離大于x，那么這個節點就不需要被檢查。