Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define INF 1000000
- using namespace std;
- double AdjMatrix[100][100];
- double AdjMatrix2[100][100];
- double parent[100][100];
- int distance;
- int pathfind(int src,int dest)
- {
- if(src==dest)
- {
- cout<<"path "<<src;
- return 0;
- }
- pathfind(src,parent[src][dest]);
- cout<<" "<<dest;
- }
- int main()
- {
- ifstream input("Flyod_warshel.txt");
- if(!input.is_open())
- {
- cout<<"File is not open"<<endl;
- }
- int totalnode,node1,node2;
- double weight;
- input>>totalnode;
- for(int i=1;i<=totalnode;i++)
- {
- for(int j=1;j<=totalnode;j++)
- {
- if(i==j)
- AdjMatrix[i][j]=0;
- else
- AdjMatrix[i][j]=INF;
- parent[i][j]=i;
- }
- }
- while(input>>node1>>node2>>weight)
- {
- AdjMatrix[node1][node2]=log(weight);
- AdjMatrix2[node1][node2]=weight;
- }
- for(int i=1;i<=totalnode;i++)
- {
- for(int j=1;j<=totalnode;j++)
- {
- cout<<AdjMatrix[i][j]<<" ";
- }
- cout<<endl;
- }
- cout<<endl;
- for(int i=1;i<=totalnode;i++)
- {
- for(int j=1;j<=totalnode;j++)
- {
- cout<<parent[i][j]<<" ";
- }
- cout<<endl;
- }
- for(int k=1;k<=totalnode;k++)
- {
- for(int i=1;i<=totalnode;i++)
- {
- for(int j=1;j<=totalnode;j++)
- {
- if(AdjMatrix[i][k]+AdjMatrix[k][j]<AdjMatrix[i][j])
- {
- AdjMatrix2[i][j]=AdjMatrix2[i][k]*AdjMatrix2[k][j];
- AdjMatrix[i][j]=AdjMatrix[i][k]+AdjMatrix[k][j];
- parent[i][j]=parent[k][j];
- }
- }
- }
- }
- int src;
- int dest;
- cout<<"ENter src and dest"<<endl;
- cin>>src>>dest;
- for(int i=1;i<=totalnode;i++)
- {
- for(int j=1;j<=totalnode;j++)
- {
- cout<<AdjMatrix[i][j]<<" ";
- }
- cout<<endl;
- }
- cout<<"Distance "<<AdjMatrix2[src][dest]<<endl;
- pathfind(src,dest);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement