Mostafizur_Rahman

dijkstra_matrix

Aug 5th, 2021
654
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b,w,y,t=0;
  4. int edge=6,node=5;
  5. vector<int>vis;
  6. bool v[50];
  7. void process(int adj[][50],int x)
  8. {
  9.     cout<<"Shortest path : ";
  10.     while(vis.size()!=node)
  11.     {
  12.         int m=1000000;
  13.         cout<<x<<" ";
  14.         for(int j=1; j<=node; j++)
  15.         {
  16.             if(t==j)
  17.                 continue;
  18.             m=min(m,adj[x][j]);
  19.         }
  20.         y=m;
  21.         for(int i=1; i<=node; i++)
  22.         {
  23.             if(adj[x][i]==y)
  24.             {
  25.                 if(v[i])
  26.                     continue;
  27.                 v[i]=true;
  28.                 vis.push_back(i);
  29.                 t=x;
  30.                 x=i;
  31.             }
  32.         }
  33.  
  34.     }
  35.     cout<<endl;
  36.  
  37. }
  38. int main()
  39. {
  40.     int adj[50][50],p;
  41.     cout<<"Enter two vertices & weight between them "<<endl;
  42.     for(int i=1; i<=edge; i++)
  43.     {
  44.         cin>>a>>b>>w;
  45.         adj[a][b]=w;
  46.         adj[b][a]=w;
  47.     }
  48.     for(int i=1; i<=edge; i++)
  49.     {
  50.         for(int j=1; j<=edge; j++)
  51.         {
  52.             if(!adj[i][j])
  53.                 adj[i][j]=1000000;//think like INF
  54.         }
  55.  
  56.     }
  57.  
  58.     cout<<"Enter starting node : ";
  59.     cin>>p;
  60.     process(adj,p);
  61.  
  62. }
  63.  
RAW Paste Data