fork download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Created by Shubham on 8/23/2016.
  5.  */
  6. class BellmanFordImpl {
  7.  
  8.     class Edge {
  9.         private int src, dest, weight;
  10.  
  11.         Edge(int v, int w, int val) {
  12.             this.src = v;
  13.             this.dest = w;
  14.             this.weight = val;
  15.         }
  16.     }
  17.  
  18.     private int V;
  19.     private int E;
  20.     private LinkedList[] adj;   //Graph representation using adjacency list
  21.     private boolean[] onQueue;  //Maininging a queue for verticies whose distTo[] have not changed.
  22.     private LinkedList<Integer> queue;
  23.     private int[] distTo;   //Distance to vertex from source
  24.     private int[] edgeTo;   //Vertex pointing to this vertex in the shortest path found yet
  25.  
  26.     BellmanFordImpl(int v) {
  27.         this.V = v;
  28.         this.E = 0;
  29.         this.adj = new LinkedList[V];
  30.         for (int i=0;i<V;i++) {
  31.             adj[i] = new LinkedList<Edge>();
  32.         }
  33.         this.onQueue = new boolean[V];
  34.         this.queue = new LinkedList<Integer>();
  35.         this.distTo = new int[V];
  36.         Arrays.fill(distTo, Integer.MAX_VALUE);
  37.         this.edgeTo = new int[V];
  38.     }
  39.  
  40.     private void addEdge(int v, int w, int weight) {
  41.         Edge e = new Edge(v, w, weight);
  42.         adj[v].add(e);
  43.     }
  44.  
  45.     private Iterable<Edge> adj(int v) {
  46.         return adj[v];
  47.     }
  48.  
  49.     private void findShortestPath(int src) {
  50.         queue.add(src);
  51.         distTo[src] = 0;
  52.         edgeTo[src] = -1;
  53.         while (!queue.isEmpty()) {
  54.             int v = queue.poll();
  55.             onQueue[v] = false;
  56.             for (Edge e : adj(v)){
  57.                 int w = e.dest;
  58.                 if (distTo[w] > distTo[v] + e.weight) {
  59.                     distTo[w] = distTo[v] + e.weight;
  60.                     edgeTo[w] = v;
  61.                 }
  62.                 if (!onQueue[w]) {
  63.                     onQueue[w] = true;
  64.                     queue.add(w);
  65.                 }
  66.             }
  67.         }
  68.     }
  69.  
  70.     private boolean hasPathTo(int v) {
  71.         return distTo[v] < Integer.MAX_VALUE;
  72.     }
  73.  
  74.     private Stack<Integer> pathTo(int v) {
  75.         Stack<Integer> st = new Stack<Integer>();
  76.         for (int i = v; i != -1; i = edgeTo[i]) {
  77.             st.push(i);
  78.         }
  79.         return st;
  80.     }
  81.  
  82.     private void printShortestPath(int src) {
  83.         System.out.println("The shortest path for source " + src + " is :");
  84.         for (int i=0; i<V; i++) {
  85.             if (hasPathTo(i)) {
  86.                 System.out.println("\nShortest path from source " + src + " to " + i + " is : " + distTo[i]);
  87.                 Stack<Integer> st = pathTo(i);
  88.                 while (!st.isEmpty()) {
  89.                     int val = st.pop();
  90.                     if (st.isEmpty()) {
  91.                         System.out.printf(val + "");
  92.                     } else {
  93.                         System.out.printf(val + "->");
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.     }
  99.  
  100.     private void findPath(int src) {
  101.         findShortestPath(src);
  102.         printShortestPath(src);
  103.     }
  104.  
  105.     public static void main(String[] args) {
  106.         BellmanFordImpl bf = new BellmanFordImpl(5);
  107.         bf.addEdge(0,1,-1);
  108.         bf.addEdge(0,2,4);
  109.         bf.addEdge(1,2,3);
  110.         bf.addEdge(1,3,2);
  111.         bf.addEdge(1,4,2);
  112.         bf.addEdge(3,1,1);
  113.         bf.addEdge(3,2,5);
  114.         bf.addEdge(4,3,-3);
  115.  
  116.         BellmanFordImpl bf2 = new BellmanFordImpl(5);
  117.         bf2.addEdge(0,1,1);
  118.         bf2.addEdge(1,2,1);
  119.         bf2.addEdge(2,3,1);
  120.         bf2.addEdge(3,4,1);
  121.         bf2.addEdge(0,3,5);
  122.         bf2.findPath(0);
  123.     }
  124. }
Success #stdin #stdout 0.05s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The shortest path for source 0 is :

Shortest path from source 0 to 0 is : 0
0
Shortest path from source 0 to 1 is : 1
0->1
Shortest path from source 0 to 2 is : 2
0->1->2
Shortest path from source 0 to 3 is : 3
0->1->2->3
Shortest path from source 0 to 4 is : 4
0->1->2->3->4
https://ideone.com/p3n9SQ
language:
Java (HotSpot 12)
created:
7 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!