Dijkstra

main.cpp

//Assignment Dijkstra algo

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <chrono>
#include "chrono_io"
#include "ratio_io"
#include "adjMatrixgenerator.cpp"
using namespace std;

class compare{  //to change priority_queue to min heap
  public:
  bool operator() (pair<int, int> a, pair<int, int> b){
    return a.second > b.second;
  }
};

void shortestpath(int current, vector<int> &from){
  if(from[current]!=-1)
    shortestpath(from[current],from);
  cout<<current<<" ";
}

void dijkstra(int source, vector< vector<Edge> > &adjacency_list, vector<bool> &visited,vector<int> &min_cost, vector<int> &from){
  visited[source] = true;
  //set cost for source
  min_cost[source] = 0;
  //min heap
  priority_queue< pair<int,int>, vector< pair<int,int> >, compare > priorityQ;

  //push into queue
  for (int i=0;i<adjacency_list.size();i++){
    priorityQ.push(make_pair(i,min_cost[i]));
  }
  // dijkstra main loop
  while(!priorityQ.empty()){
    int vertex = priorityQ.top().first;
    visited[vertex] = true;
    int cost = priorityQ.top().second;
    priorityQ.pop();
    vector<Edge> &next = adjacency_list[vertex];
    for (int i = 0; i < next.size();i++){
      int next_to = next[i].to;
      int next_cost = next[i].cost;
      int new_cost = cost + next_cost;
      // cout << "now at" << next_v << "cost "<< new_cost << endl;
      // if new cost < then existing cost
      // set path & replace cost with new cost
      if (new_cost < min_cost[next_to]) {
        from[next_to]=vertex;
        min_cost[next_to]=new_cost;
        priorityQ.push(make_pair(next_to,new_cost));
      }
    }
  }
}

/*
sample data

directed Graph
0->2|3->4|1
1->2|2->6|9
2->4|8->6|4
3->1|6->7|8
4->7|1
5->7|9->4|1
6->2|6->4|7->7|3
7->5|1

undirected Graph
0->1|3->2|2->4|6
1->0|3->3|9
2->0|2->4|9->6|1
3->1|9->5|7
4->0|6->2|9
5->3|7->7|9
6->2|1
7->5|9

*/
int main()
{
  int vertexCount = 100, edgeCount = 500;
  vector< vector<Edge> > adjList = generateAdjList(generateAdjMatrix(vertexCount,edgeCount));

  // vertexList.push_back(edge(1,3));  
  // vertexList.push_back(edge(2,2));  
  // vertexList.push_back(edge(4,6));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(0,3));
  // vertexList.push_back(edge(3,9));    
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(0,2));
  // vertexList.push_back(edge(4,9));
  // vertexList.push_back(edge(6,1));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(1,9));
  // vertexList.push_back(edge(5,7));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(0,6));
  // vertexList.push_back(edge(2,9));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(3,7));
  // vertexList.push_back(edge(7,9));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(2,1));  
  // adjList.push_back(vertexList);
  // vertexList.clear();

  // vertexList.push_back(edge(5,9));
  // adjList.push_back(vertexList);
  // vertexList.clear();

  vector<int> min_cost;
  vector<int> from;
  vector<bool> visited;
  
  int source = 0;
  vector<chrono::duration<long long, nano> > duration;
  chrono::duration<long long, nano> totalTime;

  
  for(source = 0; source < adjList.size(); source++){
    int size = adjList.size();
    visited.clear();
    visited.resize(size,false);
    min_cost.clear();
    //set cost for all
    min_cost.resize(size,INF);
    from.clear();
    //init path from to -1
    from.resize(size,-1);

    auto start = chrono::high_resolution_clock::now();
    dijkstra(source, adjList,visited, min_cost, from);
    auto end = chrono::high_resolution_clock::now();
    duration.push_back(end-start);
    cout << "Vertex\tVisited\tCost\tFrom\tShortest Path from "<< source << endl;
    for(int i = 0; i < min_cost.size(); i++){
      cout << i << "\t" << visited[i] << "\t" << min_cost[i] << "\t" <<from[i] << "\t";
      shortestpath(i,from); 
      cout << endl;
    }
    cout << "Elapsed Time : " << end-start << endl;
  }
  for(int i = 0; i < duration.size(); i++)
    totalTime += duration[i];
  cout << "Total Time : " << totalTime << endl;

  return 0;
}