Advertisement
Zhobra

Untitled

May 24th, 2022
663
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. vector<vector<pair<int,int>>> G;
  9.  
  10. void print(const vector<vector<pair<int,int>>>& G)
  11. {
  12.     int index = 0;
  13.     for (auto i = G.begin(); i != G.end(); i++, index++)
  14.     {
  15.         cout << index << ": ";
  16.         for (auto j: (*i))
  17.         {
  18.             cout << j.first << "(" << j.second << ") ";
  19.         }
  20.         cout << endl;
  21.     }
  22. }
  23.  
  24. vector<double> Dijkstra(vector<vector<pair<int,int>>>& G, int s)
  25. {
  26.     vector<double> d;
  27.     d.assign(G.size(),INFINITY);
  28.     d[s]=0;
  29.    
  30.     vector<int> T;
  31.     for (int i = 0; i < G.size(); i++)
  32.         T.push_back(i); // T = {0,1,2,...,n-1}
  33.     while (T.size()!=0)
  34.     {
  35.         int w = *(T.begin());
  36.         for (auto i : T)
  37.             if (d[i]<d[w])
  38.                 w = i;
  39.         for (auto i = T.begin(); i != T.end(); i++)
  40.             if ((*i) == w)
  41.             {
  42.                 T.erase(i);
  43.                 break;
  44.             }
  45.                
  46.    
  47.         for (auto v : T)
  48.         {
  49.             double weight = INFINITY;
  50.             for (auto i : G[w])
  51.                 if (i.first == v)
  52.                 {
  53.                     weight = i.second;
  54.                     break;
  55.                 }
  56.             if (d[v] > d[w] + weight)
  57.                 d[v] = d[w] + weight;
  58.         }
  59.     }
  60.     return d;
  61. }
  62.  
  63. int main()
  64. {
  65.     srand(time(nullptr));
  66.     //ifstream in(?);
  67.     int n = 8;
  68.     //in >> n;
  69.     for (int i = 0; i < n; i++)
  70.     {
  71.         G.push_back(vector<pair<int,int>>());
  72.         int m = rand()%n;
  73.         //in >> m;
  74.         for (int j = 0; j < m; j++)
  75.         {
  76.             int t1 = rand()%n, t2 = rand()%20;
  77.             //in >> t1 >> t2;
  78.             G[i].push_back(make_pair(t1,t2));
  79.         }
  80.     }
  81.    
  82.     print(G);
  83.    
  84.     vector<double> res = Dijkstra(G,0);
  85.    
  86.     cout << endl << endl;
  87.     for (auto i : res)
  88.     {
  89.         cout << i << endl;
  90.     }
  91.     return 0;
  92. }
  93.  
Advertisement
RAW Paste Data Copied
Advertisement