Download code

Jump to: navigation, search

Back to Dijkstra's_algorithm_(C_Plus_Plus)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

build.log

1 /tmp/litprog6404751/dijkstra_example.cpp: In function 'void DijkstraComputePaths(vertex_t, adjacency_map_t&, std::map<int, double>&, std::map<int, int>&)':
2 /tmp/litprog6404751/dijkstra_example.cpp:56:27: error: 'numeric_limits' is not a member of 'std'
3 /tmp/litprog6404751/dijkstra_example.cpp:56:48: error: expected primary-expression before 'double'
4 /tmp/litprog6404751/dijkstra_example.cpp:56:48: error: expected ';' before 'double'


hijacker
hijacker
hijacker
hijacker

dijkstra_example.cpp

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(C_Plus_Plus)?oldid=19645
 14 */
 15 
 16 #include <iostream>
 17 #include <vector>
 18 #include <string>
 19 #include <map>
 20 #include <list>
 21 #include <set>
 22 
 23 typedef int vertex_t;
 24 typedef double weight_t;
 25 
 26 struct edge {
 27     vertex_t target;
 28     weight_t weight;
 29     edge(vertex_t arg_target, weight_t arg_weight)
 30         : target(arg_target), weight(arg_weight) { }
 31 };
 32 
 33 typedef std::map<vertex_t, std::list<edge> > adjacency_map_t;
 34 
 35 
 36 template <typename T1, typename T2>
 37 struct pair_first_less
 38 {
 39     bool operator()(std::pair<T1,T2> p1, std::pair<T1,T2> p2)
 40     {
 41         return p1.first < p2.first;
 42     }
 43 };
 44 
 45 
 46 void DijkstraComputePaths(vertex_t source,
 47                           adjacency_map_t& adjacency_map,
 48                           std::map<vertex_t, weight_t>& min_distance,
 49                           std::map<vertex_t, vertex_t>& previous)
 50 {
 51     for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
 52          vertex_iter != adjacency_map.end();
 53          vertex_iter++)
 54     {
 55         vertex_t v = vertex_iter->first;
 56         min_distance[v] = std::numeric_limits< double >::infinity();
 57     }
 58     min_distance[source] = 0;
 59     std::set< std::pair<weight_t, vertex_t>,
 60               pair_first_less<weight_t, vertex_t> > vertex_queue;
 61     for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
 62          vertex_iter != adjacency_map.end();
 63          vertex_iter++)
 64     {
 65         vertex_t v = vertex_iter->first;
 66         vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));
 67     }
 68 
 69     while (!vertex_queue.empty()) {
 70         vertex_t u = vertex_queue.begin()->second;
 71         vertex_queue.erase(vertex_queue.begin());
 72 
 73         // Visit each edge exiting u
 74         for (std::list<edge>::iterator edge_iter = adjacency_map[u].begin();
 75              edge_iter != adjacency_map[u].end();
 76              edge_iter++)
 77         {
 78             vertex_t v = edge_iter->target;
 79             weight_t weight = edge_iter->weight;
 80             weight_t distance_through_u = min_distance[u] + weight;
 81 	    if (distance_through_u < min_distance[v]) {
 82 	        vertex_queue.erase(std::pair<weight_t, vertex_t>(min_distance[v], v));
 83 
 84 	        min_distance[v] = distance_through_u;
 85 	        previous[v] = u;
 86 	        vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));
 87 	    }
 88         }
 89     }
 90 }
 91 
 92 std::list<vertex_t> DijkstraGetShortestPathTo(
 93     vertex_t target, std::map<vertex_t, vertex_t>& previous)
 94 {
 95     std::list<vertex_t> path;
 96     std::map<vertex_t, vertex_t>::iterator prev;
 97     vertex_t vertex = target;
 98     path.push_front(vertex);
 99     while((prev = previous.find(vertex)) != previous.end())
100     {
101         vertex = prev->second;
102         path.push_front(vertex);
103     }
104     return path;
105 }
106 
107 int main()
108 {
109     adjacency_map_t adjacency_map;
110     std::vector<std::string> vertex_names;
111 
112     vertex_names.push_back("Harrisburg");   // 0
113     vertex_names.push_back("Baltimore");    // 1
114     vertex_names.push_back("Washington");   // 2
115     vertex_names.push_back("Philadelphia"); // 3
116     vertex_names.push_back("Binghamton");   // 4
117     vertex_names.push_back("Allentown");    // 5
118     vertex_names.push_back("New York");     // 6
119     adjacency_map[0].push_back(edge(1,  79.83));
120     adjacency_map[0].push_back(edge(5,  81.15));
121     adjacency_map[1].push_back(edge(0,  79.75));
122     adjacency_map[1].push_back(edge(2,  39.42));
123     adjacency_map[1].push_back(edge(3, 103.00));
124     adjacency_map[2].push_back(edge(1,  38.65));
125     adjacency_map[3].push_back(edge(1, 102.53));
126     adjacency_map[3].push_back(edge(5,  61.44));
127     adjacency_map[3].push_back(edge(6,  96.79));
128     adjacency_map[4].push_back(edge(5, 133.04));
129     adjacency_map[5].push_back(edge(0,  81.77));
130     adjacency_map[5].push_back(edge(3,  62.05));
131     adjacency_map[5].push_back(edge(4, 134.47));
132     adjacency_map[5].push_back(edge(6,  91.63));
133     adjacency_map[6].push_back(edge(3,  97.24));
134     adjacency_map[6].push_back(edge(5,  87.94));
135 
136     std::map<vertex_t, weight_t> min_distance;
137     std::map<vertex_t, vertex_t> previous;
138     DijkstraComputePaths(0, adjacency_map, min_distance, previous);
139     for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
140          vertex_iter != adjacency_map.end();
141          vertex_iter++)
142     {
143         vertex_t v = vertex_iter->first;
144         std::cout << "Distance to " << vertex_names[v] << ": " << min_distance[v] << std::endl;
145         std::list<vertex_t> path =
146             DijkstraGetShortestPathTo(v, previous);
147         std::list<vertex_t>::iterator path_iter = path.begin();
148         std::cout << "Path: ";
149         for( ; path_iter != path.end(); path_iter++)
150         {
151             std::cout << vertex_names[*path_iter] << " ";
152         }
153         std::cout << std::endl;
154     }
155     return 0;
156 }


hijacker
hijacker
hijacker
hijacker