做一個C++ 11 Dijkstra算法實現返回最短路徑

Question

通過Michal Forisek A C++ 11的實現Dijkstra算法的計算確實的最短距離相當快&典雅，沒有太多的代碼。但是我怎麼能回到路上？

struct edge 
{ 
    edge(const int _to, const int _len): to(_to), length(_len) 
    { 

    } 

    int to; 
    int length; 
}; 

int dijkstra(const vector< vector<edge> > &graph, int source, int target) { 
    vector<int> min_distance(graph.size(), INT_MAX); 
    min_distance[ source ] = 0; 
    set< pair<int,int> > active_vertices; 
    active_vertices.insert({0,source}); 

    while (!active_vertices.empty()) { 
     int where = active_vertices.begin()->second; 
     if (where == target) return min_distance[where]; 
     active_vertices.erase(active_vertices.begin()); 
     for (auto ed : graph[where]) 
      if (min_distance[ed.to] > min_distance[where] + ed.length) { 
       active_vertices.erase({ min_distance[ed.to], ed.to }); 
       min_distance[ed.to] = min_distance[where] + ed.length; 
       active_vertices.insert({ min_distance[ed.to], ed.to }); 
      } 
    } 
    return INT_MAX; 
} 

int main() 
{ 

    std::vector<edge> node0 {edge(1,1), edge (3,7), edge (2,1)}; 
    std::vector<edge> node1 {edge(0,1), edge (2,2), edge (3,4)}; 
    std::vector<edge> node2 {edge(1,2), edge (3,3), edge (0,1)}; 
    std::vector<edge> node3 {edge(2,3), edge (0,7), edge (1,4)}; 

    std::vector<std::vector<edge>> graph {node0, node1, node2, node3}; 

    int r = dijkstra(graph, 0, 3); 

return 0; 
} 

Answer 1

而不是返回：

目的地開始，檢查與邊緣將它的所有節點。選擇與最小距離+ ed.length到目的節點的目的地相鄰的節點。如果相鄰節點不在最小距離圖中，請忽略它。

這是您的新目的地。重複，直到你的目的地是你的來源。

基本上，你可以貪婪地回到起點，因爲你知道哪個節點最便宜到達起點。

如果您的邊緣是雙向的，或者您有方法向後查找邊緣，這樣很便宜。

否則，跟蹤最小距離地圖中的最小距離和節點可以讓您輕鬆完成。

struct edge 
{ 
    int to; 
    int length; 
}; 

using node = std::vector<edge>; 
using graph = std::vector<node>; 
void add_edge(graph& g, int start, int finish, int length) { 
    if ((int)g.size() <= (std::max)(start, finish)) 
    g.resize((std::max)(start,finish)+1); 
    g[start].push_back({finish, length}); 
    g[finish].push_back({start, length}); 
} 

using path = std::vector<int>; 

struct result { 
    int distance; 
    path p; 
}; 
result dijkstra(const graph &graph, int source, int target) { 
    std::vector<int> min_distance(graph.size(), INT_MAX); 
    min_distance[ source ] = 0; 
    std::set< std::pair<int,int> > active_vertices; 
    active_vertices.insert({0,source}); 

    while (!active_vertices.empty()) { 
    int where = active_vertices.begin()->second; 
    if (where == target) 
    { 
     int cost = min_distance[where]; 
     // std::cout << "cost is " << cost << std::endl; 
     path p{where}; 
     while (where != source) { 
     int next = where; 
     for (edge e : graph[where]) 
     { 
      // std::cout << "examine edge from " << where << "->" << e.to << " length " << e.length << ":"; 

      if (min_distance[e.to] == INT_MAX) 
      { 
      // std::cout << e.to << " unexplored" << std::endl; 
      continue; 
      } 

      if (e.length + min_distance[e.to] != min_distance[where]) 
      { 
      // std::cout << e.to << " not on path" << std::endl; 
      continue; 
      } 
      next = e.to; 
      p.push_back(next); 
      // std::cout << "backtracked to " << next << std::endl; 
      break; 
     } 
     if (where==next) 
     { 
      // std::cout << "got lost at " << where << std::endl; 
      break; 
     } 
     where = next; 
     } 
     std::reverse(p.begin(), p.end()); 
     return {cost, std::move(p)}; 
    } 
    active_vertices.erase(active_vertices.begin()); 
    for (auto ed : graph[where]) 
     if (min_distance[ed.to] > min_distance[where] + ed.length) { 
     active_vertices.erase({ min_distance[ed.to], ed.to }); 
     min_distance[ed.to] = min_distance[where] + ed.length; 
     active_vertices.insert({ min_distance[ed.to], ed.to }); 
     } 
    } 
    return {INT_MAX}; 
} 

int main() 
{ 
    graph g; 
    add_edge(g, 0, 1, 1); 
    add_edge(g, 0, 3, 7); 
    add_edge(g, 0, 2, 1); 
    add_edge(g, 1, 2, 2); 
    add_edge(g, 1, 3, 4); 
    add_edge(g, 2, 3, 3); 


    auto r = dijkstra(g, 0, 3); 
    std::cout << "cost is " << r.distance << ": "; 
    for (int x:r.p) { 
    std::cout << x << " then "; 
    } 
    std::cout << "and we are done.\n"; 

    return 0; 
} 

Live example。

Answer 2

您可以通過創建「父母」列表使其返回最短路徑。基本上，這個列表將保存你跟蹤的每個頂點的父項。父母，我的意思是，對於任何頂點，該頂點的父節點是最短路徑中的節點。當您更新min_distance列表時，還應該通過將頂點「ed.to」的父級設置爲「where」來更新「父級」列表。然後，您可以返回父母列表並通過它追蹤以找到最短路徑。只需訪問目標節點的父節點，然後順序移動，直到找到父節點爲源的節點。這是你的道路。