制作一个 c++11 Dijkstra 实现 return 最短路径

Question

Dijkstra 算法的 C++11 实现 Michal Forisek 确实可以非常快速且优雅地计算最短距离，而且代码不多。但是我怎样才能 return 路径呢？

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

您可以通过创建 "parents" 列表使其成为 return 最短路径。基本上，此列表将包含您跟踪的每个顶点的 parent。通过 parent，我的意思是对于任何顶点，该顶点的 parent 是最短路径中它之前的节点。当您更新 min_distance 列表时，您还应该通过将顶点 "ed.to" 的 parent 设置为 "where" 来更新 "parents" 列表。然后您可以 return parents 列表并追踪它以找到最短路径。只需访问目标节点的 parent，然后按顺序移动，直到找到一个 parent 是源的节点。那是你的路。

Answer 2

而不是返回：

从目的地开始，检查所有有边的节点。选择与目标相邻的节点，到目标节点的最小距离+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.

制作一个 c++11 Dijkstra 实现 return 最短路径

Make a c++11 Dijkstra Implementation return shortest Path

c++

algorithm

dijkstra

c++11