daily pastebin goal
33%
SHARE
TWEET

Untitled

a guest Jul 11th, 2018 49 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
  1. package Assignment;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.ArrayList;
  5.  
  6. public class Shortestpath {
  7.  
  8.     public double distance = 0;
  9.  
  10.     // Dijkstra's algorithm to find shortest path from s to all other nodes
  11.     public int[] dijkstra(Graph G, int s) {
  12.         final double[] dist = new double[G.id];  // shortest known distance from "s"
  13.         final int[] pred = new int[G.id];  // preceeding node in path
  14.         final boolean[] visited = new boolean[G.id]; // all false initially
  15.  
  16.         //Set all dist to Infinity
  17.         for (int i = 0; i < dist.length; i++) {
  18.             dist[i] = Integer.MAX_VALUE;
  19.         }
  20.         //Except source =0
  21.         dist[s] = 0;
  22.  
  23.         for (int i = 0; i < dist.length; i++) {
  24.             final int next = minVertex(dist, visited);
  25.             visited[next] = true;
  26.  
  27.             // The shortest path to next is dist[next] and via pred[next].
  28.  
  29.             final int[] n = new int[G.get_adjacent(G.get_vertex(next)).size()];// <<<< Buggg
  30.             // n = set of vertex id that connect with next
  31.             LinkedList<Vertex> temp = (LinkedList) G.get_adjacent(G.get_vertex(next));//get in type of linkedlist<vertex>
  32.             for (int k = 0; k < temp.size(); k++) {
  33.                 n[k] = temp.get(k).get_id();  //insert id = vertex from linkedlist
  34.             }
  35.             for (int j = 0; j < n.length; j++) {
  36.                 final int v = n[j];
  37.                 int d;
  38.                 if (G.get_edge(G.get_vertex(next), G.get_vertex(v)) == null) {
  39.                     d = (int) (dist[next]);
  40.                 } else {
  41.                     d = (int) (dist[next] + G.get_edge(G.get_vertex(next), G.get_vertex(v)).get_distance());
  42.                 }
  43.                 if (dist[v] > d) {
  44.                     dist[v] = d;
  45.                     pred[v] = next;
  46.                 }
  47.             }
  48.         }
  49.         return pred;  // (ignore pred[s]==0!)
  50.     }
  51.  
  52.     private static int minVertex(double[] dist, boolean[] v) {
  53.         double x = Integer.MAX_VALUE;
  54.         int y = -1;   // graph not connected, or no unvisited vertices
  55.         for (int i = 0; i < dist.length; i++) {
  56.             if (!v[i] && dist[i] < x) {
  57.                 y = i;
  58.                 x = dist[i];
  59.             }
  60.         }
  61.         return y;
  62.     }
  63.  
  64.     public ArrayList<Vertex> printPath(Graph G, int[] pred, int s, int e) {
  65.         ArrayList<Vertex> path = new ArrayList<Vertex>();
  66.         int x = e, i = 0;
  67.         while (x != s) {
  68.             path.add(0, G.get_vertex(x));
  69.             x = pred[x];
  70.         }
  71.         path.add(0, G.get_vertex(s));
  72.         for (i = 0; i < path.size() - 1; i++) {
  73.             distance += G.get_edge(path.get(i), path.get(i + 1)).get_distance();
  74.         }
  75.         i = 0;
  76.         return path;
  77.     }
  78. }
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