jTruBela

Bellman Ford & Dijkstra

Dec 2nd, 2021
924
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package singleSourceShortestPath;
  2.  
  3. import java.util.PriorityQueue;
  4.  
  5. /*****************************************************************
  6.  *
  7.  * CSIT212 - Graph3.java        Justin Trubela      10/12/21
  8.  *
  9.  * Purpose: Single Source Shortest Path
  10.  *
  11.  * • Task 1 (50 pts). Implement the bellman ford(int s) function as discussed in Lecture 19.
  12.  * Note: You should return an boolean value.
  13.  *
  14.  * • Task 2 (50 pts). Implement the dijkstra(int s) function as discussed in Lecture 20.
  15.  * – Hint 1: We use an adjacent matrix to represent the graph.
  16.  *  If A[i][j] = 0, it means there is no edge between the i-th and j-th node.
  17.  *  If A[i][j] != 0, then it means the weight of the edge between the i-th and j-th node.
  18.  * – Hint 2: You do not need to do any operation for the π variable in the pseudocode in Task 1 and Task 2.
  19.  *
  20.  * • Task 3 (50 pts (Extra Credit)). Implement a function to organize the
  21.  *  shortest path for each node as a string. For example, if a node 4’s shortest
  22.  *  path is 0 → 2 → 1 → 4, you can generate a string variable s =“0 →
  23.  *  2 →1 →4”. Modify the display distance() function to show the shortest
  24.  *  distance and the shortest path for each node.
  25.  * – Hint 1: You definitely need to do operation for the π variable in
  26.  *  this task. Feel free to add any class member data based on your need.
  27.  *
  28.  *****************************************************************/
  29.  
  30.  
  31.  
  32. public class Graph3 {
  33.     int n;
  34.     int[][] A;
  35.     int[] d;    //shortest distance
  36.     /**
  37.      * @param args
  38.      */
  39.    
  40.     public Graph3 () {
  41.        
  42.     }
  43.    
  44.     public Graph3 (int _n, int[][] _A) {
  45.         n = _n;
  46.         A = _A;
  47.         d = new int[n];
  48.     }
  49.    
  50.     public void initialize_single_source(int s) {
  51.         for (int i = 0; i < n; i++)
  52.             d[i] = Integer.MAX_VALUE;
  53.         d[s] = 0;
  54.     }
  55.    
  56.     public void relax (int u, int v) {
  57.         if (d[v] > (d[u] + A[u][v]))
  58.             d[v] = d[u] + A[u][v];
  59.     }
  60.    
  61.     public boolean bellman_ford (int s) {      
  62.         boolean flag = true;
  63.        
  64.         initialize_single_source(s);
  65.         for(int i=1; i<n; i++) {
  66.            
  67.             for(int j=0; j<A.length; j++) {
  68.                
  69.                 for(int k=0; k<A.length; k++) {
  70.                    
  71.                     if(A[j][k]!=s) {
  72.                        
  73.                         relax(j,k);
  74.                    
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.        
  80.         for(int i=0; i<=n-1;i++) {
  81.             for(int j=0; j<n; j++) {
  82.                 if (d[j]>d[i]+A[i][j]) {
  83.                     return flag=false;
  84.                 }
  85.             }
  86.  
  87.         }
  88.        
  89.         return flag;
  90.     }
  91.    
  92.     public void dijkstra (int s) {
  93.         PriorityQueue<PrimNode> pQ = new PriorityQueue<PrimNode>(n);
  94.        
  95.         initialize_single_source(s);
  96.  
  97.         for(int i = 0; i<A.length; i++) {
  98.             PrimNode u;
  99.             if(i==s) {
  100.                 u = new PrimNode(i,0);
  101.             }
  102.             else {
  103.                 u = new PrimNode(i, Integer.MAX_VALUE);
  104.             }
  105.             pQ.add(u); 
  106.         }
  107.        
  108.         while(!pQ.isEmpty()) {
  109.             PrimNode u = pQ.remove();
  110.            
  111.             for(int i=0; i<n; i++) {
  112.                
  113.                 for(int j=0; j<n; j++) {
  114.                    
  115.                     if(A[i][j]!=s) {
  116.                        
  117.                         relax(i, j);
  118.                    
  119.                     }
  120.                 }
  121.             }
  122.            
  123.         }
  124.        
  125.     }
  126.    
  127.     public void display_distance () {
  128.         for (int i = 0; i < n; i++)
  129.             System.out.println(i + ": " + d[i]);
  130.     }
  131.    
  132.     public static void main(String[] args) {
  133.         // TODO Auto-generated method stub
  134.         int n = 5;
  135.         int[][] A = {
  136.         {0, 6, 0, 7, 0},
  137.         {0, 0, 5, 8, -4},
  138.         {0, -2, 0, 0, 0},
  139.         {0, 0, -3, 0, 9},
  140.         {2, 0, 7, 0, 0}
  141.         };
  142.         Graph3 g1 = new Graph3(n, A);
  143.         g1.bellman_ford(0);
  144.         g1.display_distance();
  145.        
  146.         System.out.println("-----------------------");
  147.        
  148.         int[][] B = {
  149.         {0, 10, 0, 5, 0},
  150.         {0, 0, 1, 2, 0},
  151.         {0, 0, 0, 0, 4},
  152.         {0, 3, 9, 0, 2},
  153.         {7, 0, 6, 0, 0}
  154.         };
  155.         Graph3 g2 = new Graph3(n, B);
  156.         g2.dijkstra(0);
  157.         g2.display_distance();
  158.     }
  159.  
  160. }
  161.  
RAW Paste Data