C++ Dijkstra算法 - 打印邊緣名稱/類型

我目前正在研究Dijkstra的最短路徑問題。在這個項目中，我沒有具體的東西，算法是標準的（用一組對來實現），除了我需要從一個頂點到另一個頂點打印邊的類型。C++ Dijkstra算法 - 打印邊緣名稱/類型

想象一下，我有4個頂點和5個邊。存在一對頂點p（v1，v2），使得有兩個或更多連接v1和v2的邊。例如，我們想要找到從倫敦到巴黎的距離。我們知道我們都可以開車（一種邊緣），或者我們可以購買機票（另一種類型的邊緣）。我想要做的是打印邊緣的類型。

實施例：我有兩種方法可以從倫敦達到巴黎：倫敦 - >加萊 - >巴黎，分鐘時間爲5小時，由車; 倫敦 - >巴黎，最短時間1小時，乘飛機。如何打印最短時間或最小距離，如何打印路徑等等。但是，如何打印邊緣類型（運輸類型），如'乘飛機'或'乘汽車「？這裏是我嘗試過的：

struct neighbor { 

int target_vertex; 
double weight; 
int type; 
// for type: 0 - car 
// 1 - bus 
// 2 - plane 

};

但是，我仍然無法弄清楚，如何在計算最短路徑時存儲邊緣'類型'。

代碼在這裏：https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

來源

2016-11-30 oneturkmen

解決了這個問題，從一個城市到另一個城市（基本上都是城市的所有組合）預先規定了所有可能的情況。

if (choice == 1) { 
    switch (from) { 
     case 0: { 
      if (to == 1) std::cout << " by foot "; 
      if (to == 2) std::cout << " by foot -> by bus "; 
      if (to == 3) std::cout << " by air "; 
      break; 
     } 
     case 1: { 
      if (to == 0) std::cout << " by foot "; 
      if (to == 2) std::cout << " by bus "; 
      if (to == 3) std::cout << " by bus -> by car "; 
      break; 
     } 
     case 2: { 
      if (to == 0) std::cout << " by bus -> by foot "; 
      if (to == 1) std::cout << " by bus "; 
      if (to == 3) std::cout << " by car "; 
      break; 
     } 
     case 3: { 
      if (to == 1) std::cout << " by car -> by bus "; 
      if (to == 2) std::cout << " by car "; 
      if (to == 0) std::cout << " by air "; 
     } 
    }

從=起始城市。

to =我們前往的目的地。

我確定解決方案不是最好的解決方案，但對於具有少量節點和邊緣的特定情況，它適用。

來源

2016-12-09 20:02:02 oneturkmen

你已經有了這些信息，它存儲了prev_type[x]陣列英寸此數組包含您用於達到最終節點t的transport的類型。它與記憶父節點或從中到達當前節點的節點節點的陣列prev[]結合使用。因此，您從t（最終節點）開始並調用prev[t]以獲取其父項，並且比prev_type[t]將包含用於達到t的傳輸類型。繼續這種方式，直到達到s（開始）節點。

來源

2016-11-30 20:42:36 NiVeR

這是問題，它包含不存在的類型。例如，從一個城市到另一個城市，唯一的方法是乘飛機（最短）。但它說 - >「公交專機」 – oneturkmen

C++ Dijkstra算法 - 打印邊緣名稱/類型

回答

相關問題