Rosetta Code

Dijkstra's algorithm: Difference between revisions

Page Discussion

Dijkstra's algorithm (view source)

Revision as of 09:14, 13 November 2012

457 bytes removed ,  11 years ago
→‎{{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. TheWe vertexnumber the vertexes starting from 0, and represent the graph using an adjacency list (vector whose i'th element is simplythe vector of neighbors that vertex i has representededges asto) afor stringsimplicity.
 
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 <map>
#include <list>
 
Line 272 ⟶ 271:
 
 
typedef std::stringint vertex_t;
typedef intdouble weight_t;
 
const intweight_t max_weight = std::numeric_limits<intdouble>::maxinfinity();
 
struct neighbor {
Line 284 ⟶ 283:
};
 
typedef std::mapvector<vertex_t, std::vector<neighbor> > adjacency_map_tadjacency_list_t;
 
 
void DijkstraComputePaths(vertex_t source,
const adjacency_list_t &adjacency_list,
vertex_t target,
const adjacency_map_tstd::vector<weight_t> &adjacency_mapmin_distance,
std::mapvector<vertex_t, weight_t> &min_distance,previous)
std::map<vertex_t, vertex_t> &previous)
{
int n = adjacency_list.size();
for (adjacency_map_t::const_iterator vertex_iter = adjacency_map.begin();
min_distance[v] = max_weight.clear();▼
vertex_iter != adjacency_map.end();
min_distance[v2] =.resize(n, max_weight);▼
vertex_iter++)
{
vertex_t v = vertex_iter->first;
▲ min_distance[v] = max_weight;
for (std::vector<neighbor>::const_iterator neighbor_iter = vertex_iter->second.begin();
neighbor_iter != vertex_iter->second.end();
neighbor_iter++)
{▼
vertex_t v2 = neighbor_iter->target;
▲ 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());
 
if (u == target)
break;
 
// Visit each edge exiting u
const std::vector<neighbor> &neighbors = adjacency_map.find(adjacency_list[u)->second];
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 = min_distance[u]dist + weight;
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 targetvertex, const std::mapvector<vertex_t, vertex_t> &previous)
{
std::list<vertex_t> path;
for ( ; vertex != -1; vertex = previous[vertex])
std::map<vertex_t, vertex_t>::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;
}
Line 361 ⟶ 342:
{
// remember to insert edges both ways for an undirected graph
adjacency_list_t adjacency_list(6);
adjacency_map_t adjacency_map;
▲ // 0 = {a
adjacency_map["a"].push_back(neighbor("b", 7));▼
adjacency_mapadjacency_list["a"0].push_back(neighbor("c"1, 97));
adjacency_mapadjacency_list["a"0].push_back(neighbor("f"2, 149));
adjacency_mapadjacency_list["b"0].push_back(neighbor("a"5, 714));
▲ // 1 = }b
adjacency_map["b"].push_back(neighbor("c", 10));▼
adjacency_mapadjacency_list["b"1].push_back(neighbor("d"0, 157));
adjacency_mapadjacency_list["c"1].push_back(neighbor("a"2, 910));
adjacency_mapadjacency_list["c"1].push_back(neighbor("b"3, 1015));
// 2 = c
adjacency_map["c"].push_back(neighbor("d", 11));▼
adjacency_mapadjacency_list["c"2].push_back(neighbor("f"0, 29));
adjacency_mapadjacency_list["d"2].push_back(neighbor("b"1, 1510));
adjacency_mapadjacency_list["d"2].push_back(neighbor("c"3, 11));
adjacency_mapadjacency_list["d"2].push_back(neighbor("e"5, 62));
// 3 = d
adjacency_map["e"].push_back(neighbor("d", 6));▼
adjacency_mapadjacency_list["e"3].push_back(neighbor("f"1, 915));
adjacency_mapadjacency_list["f"3].push_back(neighbor("a"2, 1411));
adjacency_mapadjacency_list["f"3].push_back(neighbor("c"4, 26));
// 4 = e
adjacency_map["f"].push_back(neighbor("e", 9));▼
▲ adjacency_mapadjacency_list["a"4].push_back(neighbor("b"3, 76));
 
▲ adjacency_mapadjacency_list["b"4].push_back(neighbor("c"5, 109));
// 5 = f
▲ adjacency_mapadjacency_list["c"5].push_back(neighbor("d"0, 1114));
▲ adjacency_mapadjacency_list["e"5].push_back(neighbor("d"2, 62));
▲ adjacency_mapadjacency_list["f"5].push_back(neighbor("e"4, 9));
 
std::mapvector<vertex_t, weight_t> min_distance;
std::mapvector<vertex_t, vertex_t> previous;
DijkstraComputePaths("a"0, "e", adjacency_mapadjacency_list, min_distance, previous);
std::cout << "Distance from a0 to e4: " << min_distance["e"4] << std::endl;
std::list<vertex_t> path = DijkstraGetShortestPathTo("e"4, previous);
std::cout << "Path : ";
std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " "));
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209835"