Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|C++}}: simplified by using adjacency list and int to represent nodes
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
(→{{header|C++}}: simplified by using adjacency list and int to represent nodes) |
||
Line 252:
(Modified from [http://en.literateprograms.org/Dijkstra%27s_algorithm_%28C_Plus_Plus%29 LiteratePrograms], which is MIT/X11 licensed.)
Solution follows Dijkstra's algorithm as described elsewhere. Data like min-distance, previous node, neighbors, are kept in separate data structures instead of part of the vertex.
For the priority queue of vertexes, we use a self-balancing binary search tree (<code>std::set</code>), which should bound time complexity by O(E log V). Although C++ has heaps, without knowing the index of an element it would take linear time to find it to re-order it for a changed weight. It is not easy to keep the index of vertexes in the heap because the heap operations are opaque without callbacks. On the other hand, using a self-balancing binary search tree is efficient because it has the same log(n) complexity for insertion and removal of the head element as a binary heap. In addition, a self-balancing binary search tree also allows us to find and remove any other element in log(n) time, allowing us to perform the decrease-key step in logarithmic time by removing and re-inserting.
Line 261:
#include <vector>
#include <string>
#include <list>
Line 272 ⟶ 271:
typedef
typedef
const
struct neighbor {
Line 284 ⟶ 283:
};
typedef std::
void DijkstraComputePaths(vertex_t source,
const adjacency_list_t &adjacency_list,
std::
{
int n = adjacency_list.size();
▲ min_distance[v] = max_weight;
{▼
▲ min_distance[v2] = max_weight;
}▼
min_distance[source] = 0;
previous.clear();
previous.resize(n, -1);
std::set<std::pair<weight_t, vertex_t> > vertex_queue;
vertex_queue.insert(std::make_pair(min_distance[source], source));
Line 313 ⟶ 302:
while (!vertex_queue.empty())
{
weight_t dist = vertex_queue.begin()->first;
vertex_t u = vertex_queue.begin()->second;
vertex_queue.erase(vertex_queue.begin());
// Visit each edge exiting u
const std::vector<neighbor> &neighbors =
for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
neighbor_iter != neighbors.end();
Line 327 ⟶ 314:
vertex_t v = neighbor_iter->target;
weight_t weight = neighbor_iter->weight;
weight_t distance_through_u =
if (distance_through_u < min_distance[v]) {
vertex_queue.erase(std::make_pair(min_distance[v], v));
Line 343 ⟶ 330:
std::list<vertex_t> DijkstraGetShortestPathTo(
vertex_t
{
std::list<vertex_t> path;
for ( ; vertex != -1; vertex = previous[vertex])
path.push_front(vertex);
return path;
}
Line 361 ⟶ 342:
{
// remember to insert edges both ways for an undirected graph
adjacency_list_t adjacency_list(6);
adjacency_map["a"].push_back(neighbor("b", 7));▼
adjacency_map["b"].push_back(neighbor("c", 10));▼
// 2 = c
adjacency_map["c"].push_back(neighbor("d", 11));▼
// 3 = d
adjacency_map["e"].push_back(neighbor("d", 6));▼
// 4 = e
adjacency_map["f"].push_back(neighbor("e", 9));▼
// 5 = f
std::
std::
DijkstraComputePaths(
std::cout << "Distance from
std::list<vertex_t> path = DijkstraGetShortestPathTo(
std::cout << "Path : ";
std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " "));
|