fork download
copy 
  1. #include <bits/stdc++.h>//!IMPLEMENTING THE DFS AND BFS FOR THE FOLLOWING GRAPH
  2. #include <functional>
  3. using namespace std;
  4. //std::priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > > minheap;
  5. struct node{int data;
  6.             int weight;
  7.             node*next;};
  8. struct List{node* head;};//! this is the first element of the list to store the address of the linked list of the vertex
  9. struct graph{int noe;List* arr; };//! graph is basically giving us a pointer to the first element of the array of (linked list which stores the address of other vertex)
  10. graph* makegraph(int num)//! function to create the basic body of the graph
  11. {    //!first we need to dynamically allocate an array of linked lists , for storing "num" no. of linked lists of vertex
  12.      List* temparr=new List[num];//!creating an array of the pointers of 1st element of adjacent vertex
  13.     graph* g=new graph;
  14.     g->arr=temparr;
  15.     for(int i=0;i<num;i++)
  16.         temparr[i].head=NULL;//! second we need to dynamical create a linked list of one element point to a NULL pointer
  17.     g->noe=num;
  18.     return g;
  19.  
  20. }
  21. void add(graph* g,int startvertex,int endvertex,int weight)
  22. { //!first we need to create a node to store the vertex and the address of the next vertex
  23.     node* newnode=new node;
  24.  
  25.     //!THE UNDERNEATH STEPS ARE NOTHING SPECIAL BUT JUST ADDING AN ELEMENT TO THE FRONT OF THE LINKED LIST
  26.     newnode->data=endvertex;
  27.     newnode->weight=weight;
  28.     newnode->next=g->arr[startvertex].head;//! making the address of next in node point to the head
  29.  
  30.     //!since adding an element at the front of linked list takes O(1) time therefore we do so
  31.     g->arr[startvertex].head=newnode;//! now we make our new node the head of the linked list
  32.  
  33. //!THE UNDERNEATH STEPS NEED TO BE DONE ONLY IN THE CASE OF UNDIRECTED GRAPH
  34.     node* newnode2=new node;
  35.      newnode2->data=startvertex;
  36.      newnode2->weight=weight;
  37.      newnode2->next=g->arr[endvertex].head;
  38.      g->arr[endvertex].head=newnode2;
  39.  
  40. }
  41.  
  42.  
  43. void print(graph*g)
  44. {
  45. for(int i=0;i<g->noe;i++)
  46.    {node*temp= g->arr[i].head;
  47.     cout<<"HEAD "<< i+1<<"::";
  48.    while(temp!=NULL)
  49.        {cout<<"->"<<temp->data+1;
  50.         temp=temp->next;
  51.        }
  52.  
  53.        cout<<endl;
  54.    }
  55.  
  56. }
  57.  
  58. void dijkstra(graph*g, int startvertex)
  59. { set<pair<int,int> >distindex;
  60.   pair<int,int>start;
  61.   set<pair<int,int> >::iterator it;
  62.   distindex.insert(make_pair(0,startvertex));
  63.   for(int i=1;i<g->noe;i++)
  64.     distindex.insert(make_pair(INT_MAX,i));
  65.   while(!distindex.empty())
  66.   {
  67.    it=distindex.begin();
  68.    start=*it;
  69.    cout<<start.second<<" "<<start.first<<endl;
  70.      distindex.erase(it);
  71.     node* temp=g->arr[start.second].head;
  72.     while(temp)
  73.     { for(it=distindex.begin();it!=distindex.end();it++)
  74.        if(it->second==(temp->data)&&(temp->weight+start.first)<=it->first)
  75.         { distindex.erase(it);
  76.         distindex.insert(make_pair((temp->weight+start.first),temp->data));
  77.           break;
  78.         }
  79.       temp=temp->next;
  80.  
  81.     }
  82.  
  83.  
  84.      }
  85.  
  86. }
  87.  
  88.  
  89.  
  90. int main()
  91. {
  92.     //!IMPLEMENTING DIJKSTRA
  93.     int num=9;
  94.     graph* g=makegraph(num);
  95.     g->noe=num;
  96.  
  97.  
  98.  
  99.     add(g, 0, 1, 4);
  100.     add(g, 0, 7, 8);
  101.     add(g, 1, 2, 8);
  102.     add(g, 1, 7, 11);
  103.     add(g, 2, 3, 7);
  104.     add(g, 2, 8, 2);
  105.     add(g, 2, 5, 4);
  106.     add(g, 3, 4, 9);
  107.     add(g, 3, 5, 14);
  108.     add(g, 4, 5, 10);
  109.     add(g, 5, 6, 2);
  110.     add(g, 6, 7, 1);
  111.     add(g, 6, 8, 6);
  112.     add(g, 7, 8, 7);
  113.  
  114.    dijkstra(g, 0);
  115.  
  116.  
  117.  
  118.  
  119.  
  120. }
  121.  
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
1 4
7 8
6 9
5 11
2 12
8 14
3 19
4 21
https://ideone.com/yNE4Au
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!