daily pastebin goal
17%
SHARE
TWEET

Untitled

a guest Jan 18th, 2018 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const vector<vertex<string, int>> vertices =
  2. {
  3.     vertex<string, int>("A", {{ "B", 1 }, { "C", 4 },{ "F", 2 }}),
  4.     vertex<string, int>("B", {{ "E", 2 }}),
  5.     vertex<string, int>("C", {{ "G", 2 }, { "D", 4 }}),
  6.     vertex<string, int>("D", {}),
  7.     vertex<string, int>("E", {{ "D", 3 }}),
  8.     vertex<string, int>("F", {{ "C", 1 }, { "G", 4 }}),
  9.     vertex<string, int>("G", {{ "E", 5 }}),
  10. };
  11.    
  12. #include "stdafx.h"
  13.  
  14.     #include <unordered_map>
  15.     #include <vector>
  16.     #include <limits>
  17.     #include <algorithm>
  18.     #include <iostream>
  19.     #include <map>
  20.  
  21.     using namespace std;
  22.  
  23.     ostream& operator<<(ostream& os, const string &a)
  24.     {
  25.         os << a.c_str();
  26.         return os;
  27.     }
  28.  
  29.     template <class T, class T2>
  30.     class vertex
  31.     {
  32.     public:
  33.         T name;
  34.         unordered_map<T, T2> edges;
  35.  
  36.         vertex(T n, const unordered_map<T, T2>& e)
  37.         {
  38.             name = n;
  39.             edges = e;
  40.         }
  41.     };
  42.  
  43.     template <class T, class T2>
  44.     class graph
  45.     {
  46.         unordered_map<T, const unordered_map<T, T2>> vertices_;
  47.  
  48.     public:
  49.         graph() {}
  50.  
  51.         explicit graph(const vector<vertex<T, T2>> &vertices)
  52.         {
  53.             for (auto vertex : vertices)
  54.             {
  55.                 add_vertex(vertex.name, vertex.edges);
  56.             }
  57.         }
  58.  
  59.         void operator +=(vertex<T, T2> &v)
  60.         {
  61.             add_vertex(v.name, v.edges);
  62.         }
  63.  
  64.         void add_vertex(T name, const unordered_map<T, T2>& edges)
  65.         {
  66.             // Insert the connected nodes in unordered map
  67.             vertices_.insert(unordered_map<T, const unordered_map<T, T2>>::value_type(name, edges));
  68.         }
  69.  
  70.         vector<T> shortest_path(T start, T finish)
  71.         {
  72.             // Second arguments -> distances
  73.             // Find the smallest distance in the already in closed list and push it in -> previous
  74.             unordered_map<T, T2> distances;
  75.             unordered_map<T, T> previous;
  76.  
  77.             vector<T> nodes;    // Open list
  78.             vector<T> path;     // Closed list
  79.  
  80.             const auto comparator2 = [&](T left, T right) { return distances[left] > distances[right]; };
  81.  
  82.             // initialize distances and nodes
  83.             for (auto& vertex : vertices_)
  84.             {            
  85.                 distances[vertex.first] = (vertex.first == start) ? 0 : numeric_limits<T2>::max();
  86.                 nodes.push_back(vertex.first);
  87.             }
  88.             sort(nodes.begin(), nodes.end(), comparator2);
  89.  
  90.             // while nodes is not empty
  91.             while (!nodes.empty())
  92.             {
  93.                 // the smallest is last
  94.                 // pop it off the list
  95.                 auto smallest = nodes.back();
  96.                 nodes.pop_back();
  97.  
  98.                 // see if we have our target
  99.                 if (smallest == finish)
  100.                 {
  101.                     // unwind to get the path
  102.                     while (previous.find(smallest) != end(previous))
  103.                     {
  104.                         path.push_back(smallest);
  105.                         smallest = previous[smallest];
  106.                     }
  107.                     // exit we are done!
  108.                     break;
  109.                 }
  110.  
  111.                 // if the smallest node has not been visited the exit
  112.                 if (distances[smallest] == numeric_limits<T2>::max())
  113.                 {
  114.                     break;
  115.                 }
  116.  
  117.                 // visit neighbors
  118.                 auto needsort = false;
  119.                 for (auto& neighbor : vertices_[smallest])
  120.                 {
  121.                     // neighbor.first is the neighbors name
  122.                     // neighbor.second is the neighbors distance
  123.                     const auto alt = distances[smallest] + neighbor.second;
  124.                     if (alt < distances[neighbor.first])
  125.                     {
  126.                         distances[neighbor.first] = alt;
  127.                         previous[neighbor.first] = smallest;
  128.                         needsort = true;
  129.                     }
  130.                 }
  131.                 // re sort
  132.                 if (needsort)
  133.                     sort(nodes.begin(), nodes.end(), comparator2);
  134.             }
  135.  
  136.             cout << endl << "Shortest path:" << endl;
  137.             for (auto a : path)
  138.             {
  139.                 cout << " " << a << " distance: " << distances[a] << endl;
  140.             }
  141.             cout << " " << start << " distance: " << distances[start] << endl;
  142.             return path;
  143.         }
  144.     };
  145.  
  146.     int main()
  147.     {
  148.         const vector<vertex<string, int>> vertices =
  149.         {
  150.             vertex<string, int>("A", {{ "B", 1 }, { "C", 4 },{ "F", 2 }}),
  151.             vertex<string, int>("B", {{ "E", 2 }}),
  152.             vertex<string, int>("C", {{ "G", 2 }, { "D", 4 }}),
  153.             vertex<string, int>("D", {}),
  154.             vertex<string, int>("E", {{ "D", 3 }}),
  155.             vertex<string, int>("F", {{ "C", 1 }, { "G", 4 }}),
  156.             vertex<string, int>("G", {{ "E", 5 }}),
  157.         };
  158.  
  159.         graph<string, int> g(vertices);
  160.  
  161.         const string initNode = "A";
  162.         const string destNode = "G";
  163.  
  164.         cout << "Initial node: " << initNode << endl;
  165.         cout << "Goal node: " << destNode << endl;
  166.  
  167.         auto result = g.shortest_path(initNode, destNode);
  168.  
  169.         return 0;
  170.     }
RAW Paste Data
Top