SHARE
TWEET

Untitled

a guest Apr 24th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. struct edge {
  5.     int src;
  6.     int dst;
  7.     int weight;
  8. };
  9.  
  10. struct vertex {
  11.     vertex() { visited = false; cost = MAX; }
  12.     static const int MAX = std::numeric_limits<int>::max();
  13.  
  14.     void add_edge(int src, int dst, int weight) {
  15.         edge e {src, dst, weight };
  16.         edges.push_back(e);
  17.     }
  18.  
  19.     std::vector<edge> edges;
  20.     int cost;
  21.     bool visited;
  22. };
  23.  
  24. int next_vertex_to_visit(const std::vector<vertex>& verts) {
  25.     //find next vertex to visit for calculations, so that is a vertex
  26.     //that has not been visited before and has the lowest cost;
  27.     int cost = vertex::MAX;
  28.     int vert_idx = -1;
  29.     for (int i=0; i<verts.size(); i++) {
  30.         if (verts[i].visited == false && verts[i].cost < cost) {
  31.             cost = verts[i].cost;
  32.             vert_idx = i;
  33.         }
  34.     }
  35.     return vert_idx;
  36. }
  37.  
  38. void calculate_costs(std::vector<vertex>& verts) {
  39.     if (verts.size() == 0)
  40.         return;
  41.     verts[0].cost = 0;  //source vertex has cost of zero
  42.  
  43.     for (int n=0; n<verts.size(); n++) {
  44.         int idx = next_vertex_to_visit(verts);
  45.         for (int i=0; i<verts[idx].edges.size(); i++) {
  46.             int cost = verts[idx].cost + verts[idx].edges[i].weight;
  47.             int dst = verts[idx].edges[i].dst;
  48.             if (cost < verts[dst].cost)
  49.                 verts[dst].cost = cost;
  50.         }
  51.         verts[idx].visited = true;
  52.     }
  53. }
  54.  
  55. void print_costs(std::vector<vertex>& verts) {
  56.     for (auto v : verts) {
  57.         std::cout << v.cost << " ";
  58.     }
  59.     std::cout << std::endl;
  60. }
  61.  
  62. std::vector<vertex> create_graph() {
  63.     std::vector<vertex> verts;
  64.  
  65.     {   vertex v;
  66.         v.add_edge(0, 1, 4);
  67.         v.add_edge(0, 5, 2);
  68.         verts.push_back(v);
  69.     }
  70.     {   vertex v;
  71.         v.add_edge(1, 2, 5);
  72.         v.add_edge(1, 3, 6);
  73.         verts.push_back(v);
  74.     }
  75.     {   vertex v;
  76.         v.add_edge(2, 1, 3);
  77.         verts.push_back(v);
  78.     }
  79.     {   vertex v;
  80.         v.add_edge(3, 2, 1);
  81.         verts.push_back(v);
  82.     }
  83.     {   vertex v;
  84.         v.add_edge(4, 1, 1);
  85.         v.add_edge(4, 3, 3);
  86.         verts.push_back(v);
  87.     }
  88.     {   vertex v;
  89.         v.add_edge(5, 4, 1);
  90.         verts.push_back(v);
  91.     }
  92.  
  93.     return verts;
  94. }
  95.  
  96. int main() {
  97.     auto verts = create_graph();
  98.     calculate_costs(verts);
  99.     print_costs(verts);
  100.  
  101.     return 0;
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top