• API
• FAQ
• Tools
• Archive
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;
68.         verts.push_back(v);
69.     }
70.     {   vertex v;
73.         verts.push_back(v);
74.     }
75.     {   vertex v;
77.         verts.push_back(v);
78.     }
79.     {   vertex v;
81.         verts.push_back(v);
82.     }
83.     {   vertex v;
86.         verts.push_back(v);
87.     }
88.     {   vertex v;
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.

Top