• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Nov 22nd, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.util.Arrays;
2.
3. import java.util.Comparator;
4.
5. import java.util.PriorityQueue;
6.
7. import java.util.List;
8.
9. public class ShortestPath {
10.
11. public int weightOfShortestPath(Graph graph, int start, int end)
12.
13. {
14.
15. int distanceArray[]=new int[graph.getNodes().size()];
16.
17. //set distance of all nodes as infinite i.e max_value
18.
19. for(int i=0; i<distanceArray.length; i++)
20.
21. distanceArray[i]=Integer.MAX_VALUE;
22.
23. distanceArray[start]=0;//set distance of source as 0
24.
25. //a comparator to
26.
27. Comparator<Integer> cmp=new Comparator<Integer>()
28.
29. {
30.
31. public int compare(Integer a, Integer b)
32.
33. {
34.
35. if(distanceArray[a]<distanceArray[b])
36.
37. return -1;
38.
39. else if(distanceArray[a]==distanceArray[b])
40.
41. return 0;
42.
43. else
44.
45. return 1;
46.
47. }
48.
49. };
50.
51. //priority queue to get the minimum weight node from source
52.
53. PriorityQueue<Integer> pq=new PriorityQueue<Integer>(cmp);//min heap
54.
55. for(int i=0; i<distanceArray.length; i++)
56.
58.
59. while(!pq.isEmpty())
60.
61. {//while the priority queue is not empty
62.
63. int node=pq.remove();
64.
65. List<Edge> list=graph.getOutgoingEdges(node);//get all the outgoing edges from the node
66.
67. for(Edge edge: list)
68.
69. {//traverse over all edges
70.
71. if(pq.contains(edge.getTo()))
72.
73. {//if edge head is present in the priority queue
74.
75. if(distanceArray[node]+edge.getWeight()<distanceArray[edge.getTo()])
76.
77. {//check distance, if less than update the old distance to new distance
78.
79. distanceArray[edge.getTo()]=distanceArray[node]+edge.getWeight();
80.
81. }
82.
83. //update the priority queue
84.
85. pq.remove(edge.getTo());
86.
88.
89. }
90.
91. }
92.
93. }
94.
95. //print the minimum distance to all nodes from the start node
96.
97. System.out.println("Minimum distance to all nodes from source is: "+Arrays.toString(distanceArray));
98.
99. return distanceArray[end];//return the minimum distance from start to end node
100.
101. }
102.
103. public static void main(String ar[])
104.
105. {
106.
107. int matrix[][]= {
108.
109. {0, 3, 5, 0, 0, 0},
110.
111. {0, 0, 1, 1, 0, 0},
112.
113. {0, 0, 0, 2, 0, 0},
114.
115. {0, 0, 0, 0, 1, 3},
116.
117. {0, 0, 0, 0, 0, 0},
118.
119. {0, 0, 0, 0, 1, 0}
120.
121. };
122.
123. Graph graph=new Graph(matrix);
124.
125. //get minimum distance from 0th node to 5th node
126.
127. ShortestPath sp=new ShortestPath();
128.
129. int dis=sp.weightOfShortestPath(graph, 0, 5);
130.
131. System.out.println("The minimum distance from 0th node to 5th node is: "+dis);
132.
133. }
134.
135. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top