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.  
  57. pq.add(i);//add all the nodes to the priority queue
  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.  
  87. pq.add(edge.getTo());
  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. OK, I Understand
 
Top