本文共 14862 字，大约阅读时间需要 49 分钟。
这是我发现的难得的比较好文章，介绍Dijkstra 算法的c++程序部署。
is a that simultaneously finds the shortest path from a single vertex in a weighted graph to all other vertices in the graph, called the single-source shortest path problem. It works for directed and undirected graphs, but unlike the , requires nonnegative edge weights.
Contents
[]
[] Simple graph representation
The data structures supplied by C++'s Standard Template Library facilitate a straightforward implementation of Dijkstra's algorithm. For simplicity, we start with a simple graph representation where the vertices are numbered by sequential integers (0, 1, 2, ...) and the edge weights are doubles. We define a struct representing an edge that stores its weight and target vertex (the vertex it points to):
<<>>=
typedef int vertex_t;
typedef double weight_t;
struct edge { const vertex_t target;
const weight_t weight;
edge(vertex_t arg_target, weight_t arg_weight)
: target(arg_target), weight(arg_weight) { } };
Because we'll need to iterate over the successors of each vertex, we will find an adjacency list representation most convenient. We will represent this as an adjacency map, a mapping from each vertex to the list of edges exiting that vertex, as defined by the following typedef:
<<>>=
typedef std::map > adjacency_map_t;
<<>>=
#include
#include
[] Main algorithm
We're now prepared to define our method. We separate the computation into two stages:
- Compute the minimum distance from the source to each vertex in the graph. Simultaneously, keep track of the
previous map, which for each vertex v gives the previous vertex on the shortest path from the source vertex to v. This is the expensive step. - Later, any time we want to find a particular shortest path between the source vertex and a given vertex, we use the previous array to quickly construct it.
For the first part, we write DijkstraComputePaths, which takes two input parameters and two output parameters:
- source (in): The source vertex from which all shortest paths are found
- adjacency_map (in): The adjacency map specifying the connection between vertices and edge weights.
- min_distance (out): Will receive the shortest distance from
source to each vertex in the graph. - previous (out): Receives a map that can be passed back into
DijkstraGetShortestPathTo() later on to quickly get a shortest path from the source vertex to any desired vertex.
<<>>=
void DijkstraComputePaths(vertex_t source,
const adjacency_map_t &adjacency_map,
std::map &min_distance,
std::map &previous)
{
min_distance[source] = 0;
// Visit each edge exiting u
const std::list &edges = adjacency_map.find(u)->second;
for (std::list ::const_iterator edge_iter = edges.begin();
edge_iter != edges.end();
edge_iter++)
{ vertex_t v = edge_iter->target;
weight_t weight = edge_iter->weight;
}
}
}
The outline of how the function works is shown above: we visit each vertex, looping over its out-edges and adjusting min_distance as necessary. The critical operation is relaxing the edges, which is based on the following formula:
if (u, v) is an edge and u is on the shortest path to v, d(u) + w(u,v) = d(v).
In other words, we can reach v by going from the source to u, then following the edge (u,v). Eventually, we will visit every predecessor of v reachable from the source. The shortest path goes through one of these. We keep track of the shortest distance seen so far by setting min_distance and the vertex it went through by setting previous:
<<>>=
weight_t distance_through_u = min_distance[u] + weight;
if (distance_through_u < min_distance[v]) {
min_distance[v] = distance_through_u;
previous[v] = u;
}
Note that the original description of Dijkstra's algorithm involves remembering that when a vertex is "done" (i.e. we have gone through an iteration of the loop with u = that vertex), we put it in a set of "visited" vertices, so that if we reach it again we can skip it. However, it is not really necessary to do this specially, as it is guaranteed that if we re-reach a "done" vertex, the new distance to it will never be lessthan its original min distance, so the relaxation condition will always fail in this case which will also cause it to be skipped.
We also need to initialize the output parameters so that at first all min distances are positive infinity (as large as possible). We can visit all vertices by iterating over the keys of adjacency_map, and then iterating over the elements in the values of adjacency_map. This is needed since this is a directed graph, and so there may be vertices without any outgoing edges (i.e. sinks) whose min distance still must be set to positive infinity.
<<>>=
for (adjacency_map_t::const_iterator vertex_iter = adjacency_map.begin();
vertex_iter != adjacency_map.end();
vertex_iter++)
{ vertex_t v = vertex_iter->first;
min_distance[v] = std::numeric_limits< double >::infinity();
for (std::list ::const_iterator edge_iter = vertex_iter->second.begin();
edge_iter != vertex_iter->second.end();
edge_iter++)
{ vertex_t v2 = edge_iter->target;
min_distance[v2] = std::numeric_limits< double >::infinity();
}
}
<<>>=
#include // for numeric_limits
Finally, we need a way to visit the vertices in order of their minimum distance. We could do this using a heap data structure, but later on we will also need to decrease the distance of particular vertices, which will involve re-ordering that vertex in the heap. However, finding a particular element in a heap is a linear-time operation. To avoid this, we instead use a self-balancing binary search tree, which will also allow us to find the vertex of minimum distance, as well as find any particular vertex, quickly. We will use a std::set of pairs, where each pair contains a vertex v along with its minimum distancemin_distance[v]. Fortunately, C++'s std::pair class already implements an ordering, which orders lexicographically (by first element, then by second element), which will work fine for us, as long as we use the distance as the first element of the pair.
We don't need to put all the vertices into the priority queue to start with. We only add them as they are reached.
<<>>=
std::set< std::pair > vertex_queue;
vertex_queue.insert(std::make_pair(min_distance[source], source));
while (!vertex_queue.empty())
{ vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());
<<>>=
#include
#include // for pair
We access and remove the smallest element using begin(), which works because the set is ordered by minimum distance. If we change a vertex's minimum distance, we must update its key in the map as well (if we are reaching the vertex for the first time, it won't be in the queue, and erase() will do nothing):
<<>>=
vertex_queue.erase(std::make_pair(min_distance[v], v));
<<>>=
vertex_queue.insert(std::make_pair(min_distance[v], v));
This completes DijkstraComputePaths(). DijkstraGetShortestPathTo() is much simpler, just following the linked list in the previous map from the target back to the source:
<<>>=
std::list DijkstraGetShortestPathTo(
vertex_t target, const std::map &previous)
{ std::list path;
std::map ::const_iterator prev;
vertex_t vertex = target;
path.push_front(vertex);
while((prev = previous.find(vertex)) != previous.end())
{ vertex = prev->second;
path.push_front(vertex);
}
return path;
}
[] Sample code
Here's some code demonstrating how we use the above functions:
<<>>=
#include
#include
#include
int main()
{ adjacency_map_t adjacency_map;
std::vector vertex_names;
std::map min_distance;
std::map previous;
DijkstraComputePaths(0, adjacency_map, min_distance, previous);
return 0;
}
Printing out shortest paths is just a matter of iterating over the vertices and callingDijkstraGetShortestPathTo() on each:
<<>>=
for (adjacency_map_t::const_iterator vertex_iter = adjacency_map.begin();
vertex_iter != adjacency_map.end();
vertex_iter++)
{ vertex_t v = vertex_iter->first;
std::cout << "Distance to " << vertex_names[v] << ": " << min_distance[v] << std::endl;
std::list path =
DijkstraGetShortestPathTo(v, previous);
std::list ::const_iterator path_iter = path.begin();
std::cout << "Path: ";
for( ; path_iter != path.end(); path_iter++)
{ std::cout << vertex_names[*path_iter] << " ";
}
std::cout << std::endl;
}
For this example, we choose vertices corresponding to some East Coast U.S. cities. We add edges corresponding to interstate highways, with the edge weight set to the driving distance between the cities in miles as determined by Mapquest (note that edges are directed, so if we want an "undirected" graph, we would need to add edges going both ways):
<<>>=
vertex_names.push_back("Harrisburg"); // 0 vertex_names.push_back("Baltimore"); // 1 vertex_names.push_back("Washington"); // 2 vertex_names.push_back("Philadelphia"); // 3 vertex_names.push_back("Binghamton"); // 4 vertex_names.push_back("Allentown"); // 5 vertex_names.push_back("New York"); // 6 adjacency_map[0].push_back(edge(1, 79.83));
adjacency_map[0].push_back(edge(5, 81.15));
adjacency_map[1].push_back(edge(0, 79.75));
adjacency_map[1].push_back(edge(2, 39.42));
adjacency_map[1].push_back(edge(3, 103.00));
adjacency_map[2].push_back(edge(1, 38.65));
adjacency_map[3].push_back(edge(1, 102.53));
adjacency_map[3].push_back(edge(5, 61.44));
adjacency_map[3].push_back(edge(6, 96.79));
adjacency_map[4].push_back(edge(5, 133.04));
adjacency_map[5].push_back(edge(0, 81.77));
adjacency_map[5].push_back(edge(3, 62.05));
adjacency_map[5].push_back(edge(4, 134.47));
adjacency_map[5].push_back(edge(6, 91.63));
adjacency_map[6].push_back(edge(3, 97.24));
adjacency_map[6].push_back(edge(5, 87.94));
[] Alternatives
In an application that does a lot of graph manipulation, a good option is the , which includes .
我修改的代码：
1: #include
2: #include
3: #include
4: #include
5: #include
6: #include
7: //#include
8: #include
9: #include
10: #include
11: #include
12: //#include // priority_queue
13: //#include // greater
14:
15: using namespace std;
16: typedef int vertex_t;
17: typedef int weight_t;
18:
19: struct edge
20: { 21: const vertex_t target;
22: const weight_t weight;
23: edge (vertex_t arg_target, weight_t arg_weight)
24: : target(arg_target), weight( arg_weight) { } 25: };
26:
27: typedef map > adjacency_map_t;
28:
29:
30: void DijkstraComputePaths(vertex_t source,
31: const adjacency_map_t &adjacency_map,
32: map &min_distance,
33: map &previous);
34: istream& readData(istream &in, adjacency_map_t &adjacency_map);
35: void showResult(const vector &vec, map &min_distance);
36:
37: int main(){ 38: //fstream fin ("data2.txt"); 39: fstream fin("dijkstraData.txt"); 40: adjacency_map_t adjacency_map;
41: readData(fin, adjacency_map);
42:
43: map min_distance;
44: map previous;
45:
46: DijkstraComputePaths(1, adjacency_map, min_distance, previous);
47:
48: int tmp[] = {7, 37, 59, 82, 99, 115, 133, 165, 188, 197}; 49: vector vec_res(tmp, tmp + sizeof(tmp) / sizeof(int) );
50: showResult(vec_res, min_distance);
51: return 0;
52: }
53:
54:
55:
56:
57: void showResult(const vector &vec, map &min_distance){
58: for (auto iter = vec.cbegin(); iter != vec.cend(); iter++){ 59: cout << min_distance[*iter] << ",";
60: }
61: }
62:
63:
64: istream& readData(istream &in, adjacency_map_t &adjacency_map){ 65: string line;
66: vertex_t vertex1, vertex2;
67: weight_t weight;
68: //istringstream ss;
69:
70: while ( getline(in, line)){ 71: istringstream ss(line);
72: ss >> vertex1;
73: while ( ss >> vertex2 >> weight){ 74: adjacency_map[vertex1].push_back( edge(vertex2, weight));
75: adjacency_map[vertex2].push_back( edge(vertex1, weight));
76: }
77: }
78: cout << "Reading data completes" << endl;
79: return in;
80: }
81:
82:
83: void DijkstraComputePaths(vertex_t source,
84: const adjacency_map_t &adjacency_map,
85: map &min_distance,
86: map &previous)
87: { 88: //map explorerd;
89: for (auto vertex_iter = adjacency_map.begin(); vertex_iter != adjacency_map.end(); vertex_iter++)
90: { 91: vertex_t v = vertex_iter->first;
92: min_distance[v] = 1000000;
93: //explorerd[v] = false;
94: // for (auto edge_iter = vertex_iter->second.begin();
95: // edge_iter != vertex_iter->second.end();
96: // edge_iter++)
97: // { 98: // vertex_t v2 = edge_iter->target;
99: // min_distance[v2] = 1000000;
100: // }
101: }
102: min_distance[source] = 0;
103: set< pair > vertex_queue;
104:
105: vertex_queue.insert(make_pair(min_distance[source], source));
106: while (!vertex_queue.empty())
107: { 108: vertex_t u = vertex_queue.begin()->second;
109: vertex_queue.erase(vertex_queue.begin());
110:
111:
112: // Visit each edge exiting u
113: const list &edges = adjacency_map.find(u)->second;
114: for (auto edge_iter = edges.begin();
115: edge_iter != edges.end();
116: edge_iter++)
117: { 118: vertex_t v = edge_iter->target;
119: //if (explorerd[v]) continue;
120: //explorerd[v] = true;
121: weight_t weight = edge_iter->weight;
122: weight_t distance_through_u = min_distance[u] + weight;
123: if (distance_through_u < min_distance[v]) { 124: vertex_queue.erase(make_pair(min_distance[v], v));
125: min_distance[v] = distance_through_u;
126: previous[v] = u;
127: vertex_queue.insert(make_pair(min_distance[v], v));
128: }
129: }
130: }
131: }
测试数据
//data1.txt
1 2,3 3,3
2 3,1 4,2
3 4,50
4
//result
1 0 []
2 3 [2]
3 3 [3]
4 5 [2, 4]
转载地址：http://uwuii.baihongyu.com/