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
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.             }
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