Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- struct edge {
- int src;
- int dst;
- int weight;
- };
- struct vertex {
- vertex() { visited = false; cost = MAX; }
- static const int MAX = std::numeric_limits<int>::max();
- void add_edge(int src, int dst, int weight) {
- edge e {src, dst, weight };
- edges.push_back(e);
- }
- std::vector<edge> edges;
- int cost;
- bool visited;
- };
- int next_vertex_to_visit(const std::vector<vertex>& verts) {
- //find next vertex to visit for calculations, so that is a vertex
- //that has not been visited before and has the lowest cost;
- int cost = vertex::MAX;
- int vert_idx = -1;
- for (int i=0; i<verts.size(); i++) {
- if (verts[i].visited == false && verts[i].cost < cost) {
- cost = verts[i].cost;
- vert_idx = i;
- }
- }
- return vert_idx;
- }
- void calculate_costs(std::vector<vertex>& verts) {
- if (verts.size() == 0)
- return;
- verts[0].cost = 0; //source vertex has cost of zero
- for (int n=0; n<verts.size(); n++) {
- int idx = next_vertex_to_visit(verts);
- for (int i=0; i<verts[idx].edges.size(); i++) {
- int cost = verts[idx].cost + verts[idx].edges[i].weight;
- int dst = verts[idx].edges[i].dst;
- if (cost < verts[dst].cost)
- verts[dst].cost = cost;
- }
- verts[idx].visited = true;
- }
- }
- void print_costs(std::vector<vertex>& verts) {
- for (auto v : verts) {
- std::cout << v.cost << " ";
- }
- std::cout << std::endl;
- }
- std::vector<vertex> create_graph() {
- std::vector<vertex> verts;
- { vertex v;
- v.add_edge(0, 1, 4);
- v.add_edge(0, 5, 2);
- verts.push_back(v);
- }
- { vertex v;
- v.add_edge(1, 2, 5);
- v.add_edge(1, 3, 6);
- verts.push_back(v);
- }
- { vertex v;
- v.add_edge(2, 1, 3);
- verts.push_back(v);
- }
- { vertex v;
- v.add_edge(3, 2, 1);
- verts.push_back(v);
- }
- { vertex v;
- v.add_edge(4, 1, 1);
- v.add_edge(4, 3, 3);
- verts.push_back(v);
- }
- { vertex v;
- v.add_edge(5, 4, 1);
- verts.push_back(v);
- }
- return verts;
- }
- int main() {
- auto verts = create_graph();
- calculate_costs(verts);
- print_costs(verts);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement