It works on negative cycle.
Implemented Code:
Time Complexity:
O([E].[V])
Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html
It works on negative cycle.
Implemented Code:
Time Complexity:
O([E].[V])
Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html
Posted in Algo Unsolved, Bellman Ford, Single Source Shortest Path
Tagged not greedy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> using namespace std; int main(){ int cost[10][10],path[10][10],i,j,n,p,v,min,index=1; int distance[10],row,column; cout<<"Enter no. of nodes: "; cin>>n; cout<<"Enter cost matrix: \n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>cost[i][j]; } } printf("Enter the node you want to visit:"); cin>>v; printf("Enter the path for the selected node:"); cin>>p; cout<<"Enter the path matrix: \n"; for(i=1;i<=p;i++) { for(j=1;j<=n;j++) { cin>>path[i][j]; } } for(i=1;i<=p;i++){ distance[i]=0; row=1; for(j=1;j<=n;j++) { if(row!=v) { column=path[i][j+1]; distance[i]=distance[i]+cost[row][column]; } row=column; } } min=distance[1]; for(i=1;i<=p;i++) { if(distance[i]<=min) { min=distance[i]; index=i; } } cout<<"The minimum distance is:"; cout<<min; for(i=1;i<=n;i++){ if(path[index][i]!=0) { printf("-->%d",path[index][i]); } } } |
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
Enter no. of nodes: 5 Enter cost matrix: 0 4 0 8 0 4 0 3 0 0 0 3 0 4 0 8 0 4 0 7 0 0 0 7 0 Enter the node you want to visit:5 Enter the path for the selected node:2 Enter the path matrix: 1 2 3 4 5 1 4 5 0 0 The minimum distance is:15-->1-->4-->5 |
Complexity:
O(E+V^2)
We are using here adjacency matrix list
Posted in Dijkstra, Graph, Single Source Shortest Path