有向圖中從一個頂點到另一個頂點的最短路徑

Question

我的圖形很直接，而且非常大。圖中的頂點表示城鎮，邊緣表示從城鎮到城鎮的公交路線。目標是找到從一個頂點到另一個頂點的路徑。該算法考慮到總線之間的傳輸時間非常重要。

我會使用Dijkstra的算法，但它從整個圖表中找到並找到一種方法。我需要從頂點到頂點找到一些「最好」的方法。我用最短的轉移時間來表示「最好的」，但這不是最重要的一點。

Answer 1

改變巴士的「轉換時間」是一個重要的變量，並且最容易表達爲圖中的額外頂點。假設邊上的權重表示總線之間的傳輸時間，還可以使用節點和邊來表示兩條總線之間的傳輸時間。

Answer 2

即時通訊術語不確定，但有許多時間依賴的高速公路層次結構工作，如goldberg，sanders等，您可以在google（dblp或任何科學電子圖書館）上進行搜索。對於大陸尺寸的靜態數據集，它們要快上千倍，適用於動態和靜態場景。

Answer 3

如果您需要查找多條最短路徑，請參閱this question。