• API
• FAQ
• Tools
• Archive
daily pastebin goal
33%
SHARE
TWEET

# Untitled

a guest Jul 11th, 2018 49 Never
ENDING IN00days00hours00mins00secs
1. package Assignment;
2.
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
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) {
69.             x = pred[x];
70.         }
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.

Top