86 lines
2.4 KiB
Java
86 lines
2.4 KiB
Java
import java.util.*;
|
|
public class bellmanFord{
|
|
static class Edge{
|
|
int src, dest, weigh;
|
|
Edge(int s, int d, int w){
|
|
src = s;
|
|
dest = d;
|
|
weigh = w;
|
|
}
|
|
}
|
|
static void printPath(int vertex, int[] parent){
|
|
if(vertex==-1) return;
|
|
printPath(parent[vertex], parent);
|
|
System.out.print(vertex+" ");
|
|
|
|
}
|
|
public static void main(String[] args){
|
|
Scanner sc = new Scanner(System.in);
|
|
System.out.print("Enter no. of vertices and edges: ");
|
|
int n = sc.nextInt();
|
|
int e = sc.nextInt();
|
|
int[] parent = new int[n];
|
|
Edge[] edges = new Edge[e];
|
|
int[] dist = new int[n];
|
|
|
|
System.out.print("Enter the edges(src dest weight): ");
|
|
for(int i=0;i<e;i++){
|
|
int s = sc.nextInt();
|
|
int d = sc.nextInt();
|
|
int w = sc.nextInt();
|
|
edges[i] = new Edge(s,d,w);
|
|
|
|
}
|
|
|
|
System.out.println("\nEnter source vertex: ");
|
|
int s = sc.nextInt();
|
|
|
|
for(int i=0;i<n;i++){
|
|
dist[i] = 999;
|
|
parent[i] = -1;
|
|
}
|
|
dist[s] = 0;
|
|
|
|
for(int i=1;i<=n-1;i++){
|
|
for(int j=0;j<e;j++){
|
|
int sr = edges[j].src;
|
|
int d = edges[j].dest;
|
|
int w = edges[j].weigh;
|
|
if(dist[sr]!=999 && dist[sr] + w < dist[d]){
|
|
dist[d] = dist[sr]+w;
|
|
parent[d] = sr;
|
|
}
|
|
|
|
|
|
}
|
|
}
|
|
boolean negcycle = false;
|
|
|
|
for(int j=0;j<e;j++){
|
|
int sr = edges[j].src;
|
|
int d = edges[j].dest;
|
|
int w = edges[j].weigh;
|
|
if(dist[sr]!=999 && dist[sr] + w < dist[d]){
|
|
dist[d] = dist[sr]+w;
|
|
negcycle = true;
|
|
break;
|
|
|
|
}
|
|
}
|
|
if(negcycle){
|
|
System.out.println("\nNegative cycle exists.");
|
|
|
|
}else{
|
|
System.out.println("\nShortest paths from source vertex " + s + ":\n");
|
|
for(int i=0;i<n;i++){
|
|
System.out.println("vertex: "+i);
|
|
System.out.println("Cost: "+ dist[i]);
|
|
System.out.println("Path: ");
|
|
printPath(i, parent);
|
|
System.out.println();
|
|
}
|
|
}
|
|
sc.close();
|
|
}
|
|
}
|