Dijkstra’s algorithm with C++
Dijkstra’s algorithm is an algorithm for finding the shortest path in a graph. First drawing the graph:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
import networkx as nx import matplotlib.pyplot as plt from networkx.drawing.nx_agraph import write_dot, graphviz_layout def coloring_tree(G): visited_list=[] for i in G.nodes(): visited_list.append( g.nodes[i]['visited'] ) graph_color_map=[] for i in visited_list: graph_color_map.append('red') pos =graphviz_layout(G, prog='dot') labels = nx.get_edge_attributes(G,'weight') nx.draw(G,pos,with_labels=True, arrows=True, node_color = graph_color_map) nx.draw_networkx_edge_labels(G, pos,edge_labels=labels) plt.show() return g=nx.DiGraph() g.add_node('a',visited=False) g.add_node('b',visited=False) g.add_node('c',visited=False) g.add_node('d',visited=False) g.add_node('e',visited=False) g.add_node('f',visited=False) g.add_node('g',visited=False) g.add_node('h',visited=False) g.add_node('i',visited=False) g.add_edge('a','b',weight=4) g.add_edge('a','h',weight=8) g.add_edge('b','a',weight=4) g.add_edge('b','c',weight=8) g.add_edge('b','h',weight=11) g.add_edge('c','b',weight=8) g.add_edge('c','d',weight=7) g.add_edge('c','f',weight=4) g.add_edge('c','i',weight=2) g.add_edge('d','d',weight=7) g.add_edge('d','e',weight=9) g.add_edge('d','f',weight=14) g.add_edge('e','d',weight=9) g.add_edge('e','f',weight=10) g.add_edge('f','c',weight=4) g.add_edge('f','d',weight=14) g.add_edge('f','e',weight=10) g.add_edge('f','g',weight=2) g.add_edge('g','f',weight=2) g.add_edge('g','h',weight=1) g.add_edge('g','i',weight=6) g.add_edge('h','a',weight=8) g.add_edge('g','b',weight=11) g.add_edge('h','g',weight=1) g.add_edge('h','i',weight=7) g.add_edge('i','c',weight=2) g.add_edge('i','g',weight=6) g.add_edge('i','h',weight=7) coloring_tree(g) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include <iostream> #include <vector> #include <string> #include <list> #include <limits> // for numeric_limits #include <set> #include <utility> // for pair #include <algorithm> #include <iterator> typedef int vertex_t; typedef double weight_t; const weight_t max_weight = std::numeric_limits<double>::infinity(); struct neighbor { vertex_t target; weight_t weight; neighbor(vertex_t arg_target, weight_t arg_weight) : target(arg_target), weight(arg_weight) { } }; typedef std::vector<std::vector<neighbor> > adjacency_list_t; void DijkstraComputePaths(vertex_t source, const adjacency_list_t &adjacency_list, std::vector<weight_t> &min_distance, std::vector<vertex_t> &previous) { int n = adjacency_list.size(); min_distance.clear(); min_distance.resize(n, 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)); 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 = adjacency_list[u]; for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin(); neighbor_iter != neighbors.end(); neighbor_iter++) { vertex_t v = neighbor_iter->target; weight_t weight = neighbor_iter->weight; weight_t distance_through_u = dist + weight; if (distance_through_u < min_distance[v]) { vertex_queue.erase(std::make_pair(min_distance[v], v)); min_distance[v] = distance_through_u; previous[v] = u; vertex_queue.insert(std::make_pair(min_distance[v], v)); } } } } std::list<vertex_t> DijkstraGetShortestPathTo( vertex_t vertex, const std::vector<vertex_t> &previous) { std::list<vertex_t> path; for ( ; vertex != -1; vertex = previous[vertex]) path.push_front(vertex); return path; } int main() { adjacency_list_t adjacency_list(9); adjacency_list[0].push_back(neighbor(1, 4)); adjacency_list[0].push_back(neighbor(7, 8)); adjacency_list[1].push_back(neighbor(0, 4)); adjacency_list[1].push_back(neighbor(2, 8)); adjacency_list[1].push_back(neighbor(7, 11)); adjacency_list[2].push_back(neighbor(1, 8)); adjacency_list[2].push_back(neighbor(3, 7)); adjacency_list[2].push_back(neighbor(5, 4)); adjacency_list[2].push_back(neighbor(8, 2)); adjacency_list[3].push_back(neighbor(3, 7)); adjacency_list[3].push_back(neighbor(4, 9)); adjacency_list[3].push_back(neighbor(5, 14)); adjacency_list[4].push_back(neighbor(3, 9)); adjacency_list[4].push_back(neighbor(5, 10)); adjacency_list[5].push_back(neighbor(2, 4)); adjacency_list[5].push_back(neighbor(3, 14)); adjacency_list[5].push_back(neighbor(4, 10)); adjacency_list[5].push_back(neighbor(6, 2)); adjacency_list[6].push_back(neighbor(5, 2)); adjacency_list[6].push_back(neighbor(7, 1)); adjacency_list[6].push_back(neighbor(8, 6)); adjacency_list[7].push_back(neighbor(0, 9)); adjacency_list[7].push_back(neighbor(1, 9)); adjacency_list[7].push_back(neighbor(6, 9)); adjacency_list[7].push_back(neighbor(8, 9)); adjacency_list[8].push_back(neighbor(2, 2)); adjacency_list[8].push_back(neighbor(6, 6)); adjacency_list[8].push_back(neighbor(7, 7)); std::vector<weight_t> min_distance; std::vector<vertex_t> previous; DijkstraComputePaths(0, adjacency_list, min_distance, previous); std::cout << "Distance from 0 to 5: " << min_distance[5] << std::endl; std::list<vertex_t> path = DijkstraGetShortestPathTo(5, previous); std::cout << "Path : "; std::copy(path.begin(), path.end(), std::ostream_iterator<vertex_t>(std::cout, " ")); std::cout << std::endl; return 0; } |
|
1 2 |
Distance from 0 to 5: 16 Path : 0 1 2 5 |
ref [1]
Dijkstra’s algorithm with C++ Read More »
