Michal Forisek对Dijkstra算法的C++11实现确实非常快速和优雅地计算了最短的距离，没有太多的代码。但是我怎样才能返回路径呢？
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;
}
您可以通过创建"父"列表使其返回最短路径。基本上，此列表将保存您跟踪的每个顶点的父级。父级，我的意思是，对于任何顶点，该顶点的父级是最短路径中它前面的节点。更新min_distance列表时，还应通过将顶点"ed.to"的父项设置为"位置"来更新"父项"列表。然后，您可以返回父列表并跟踪它以找到最短路径。只需访问目标节点的父节点，然后按顺序移动，直到找到父节点是源的节点。那是你的道路。
而不是返回：
从目标开始，检查具有指向该目标的边缘的所有节点。 选取与目标节点相邻的节点，其最小距离+ed.长度为目标节点。 如果相邻节点不在最小距离映射中，请忽略它。
这是您的新目的地。 重复此操作，直到您的目的地是您的源。
基本上你可以贪婪地回到起点，因为你知道哪个节点最便宜
。如果您的边是双向的，或者如果您有办法向后查找边缘，则这很便宜。
否则，在最小距离地图中跟踪最小距离和节点可以让您同样轻松地完成此操作。
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;
}
活生生的例子。