@Test public void testDijkstra() { System.out.println("Dijkstra"); double[][] wt = { {0.00, 0.41, 0.82, 0.86, 0.50, 0.29}, {1.13, 0.00, 0.51, 0.68, 0.32, 1.06}, {0.95, 1.17, 0.00, 0.50, 1.09, 0.88}, {0.45, 0.67, 0.91, 0.00, 0.59, 0.38}, {0.81, 1.03, 0.32, 0.36, 0.00, 0.74}, {1.02, 0.29, 0.53, 0.57, 0.21, 0.00}, }; Graph graph = new AdjacencyList(6, true); graph.addEdge(0, 1, 0.41); graph.addEdge(1, 2, 0.51); graph.addEdge(2, 3, 0.50); graph.addEdge(4, 3, 0.36); graph.addEdge(3, 5, 0.38); graph.addEdge(3, 0, 0.45); graph.addEdge(0, 5, 0.29); graph.addEdge(5, 4, 0.21); graph.addEdge(1, 4, 0.32); graph.addEdge(4, 2, 0.32); graph.addEdge(5, 1, 0.29); double[][] wt2 = graph.dijkstra(); assertTrue(MathEx.equals(wt, wt2)); }
@Override public double[] dijkstra(int s) { double[] wt = new double[n]; Arrays.fill(wt, Double.POSITIVE_INFINITY); PriorityQueue queue = new PriorityQueue(wt); for (int v = 0; v < n; v++) { queue.insert(v); } wt[s] = 0.0; queue.lower(s); while (!queue.empty()) { int v = queue.poll(); if (!Double.isInfinite(wt[v])) { for (Edge edge : graph[v]) { int w = edge.v2; if (!digraph && w == v) { w = edge.v1; } double p = wt[v] + edge.weight; if (p < wt[w]) { wt[w] = p; queue.lower(w); } } } } return wt; }
AdjacencyList implements Graph { @Override public double[] dijkstra(int s) { double[] wt = new double[n]; Arrays.fill(wt, Double.POSITIVE_INFINITY); PriorityQueue queue = new PriorityQueue(wt); for (int v = 0; v < n; v++) { queue.insert(v); } wt[s] = 0.0; queue.lower(s); while (!queue.empty()) { int v = queue.poll(); if (!Double.isInfinite(wt[v])) { for (Edge edge : graph[v]) { int w = edge.v2; if (!digraph && w == v) { w = edge.v1; } double p = wt[v] + edge.weight; if (p < wt[w]) { wt[w] = p; queue.lower(w); } } } } return wt; } }
AdjacencyList implements Graph { @Override public double[] dijkstra(int s) { double[] wt = new double[n]; Arrays.fill(wt, Double.POSITIVE_INFINITY); PriorityQueue queue = new PriorityQueue(wt); for (int v = 0; v < n; v++) { queue.insert(v); } wt[s] = 0.0; queue.lower(s); while (!queue.empty()) { int v = queue.poll(); if (!Double.isInfinite(wt[v])) { for (Edge edge : graph[v]) { int w = edge.v2; if (!digraph && w == v) { w = edge.v1; } double p = wt[v] + edge.weight; if (p < wt[w]) { wt[w] = p; queue.lower(w); } } } } return wt; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); }
AdjacencyList implements Graph { @Override public double[] dijkstra(int s) { double[] wt = new double[n]; Arrays.fill(wt, Double.POSITIVE_INFINITY); PriorityQueue queue = new PriorityQueue(wt); for (int v = 0; v < n; v++) { queue.insert(v); } wt[s] = 0.0; queue.lower(s); while (!queue.empty()) { int v = queue.poll(); if (!Double.isInfinite(wt[v])) { for (Edge edge : graph[v]) { int w = edge.v2; if (!digraph && w == v) { w = edge.v1; } double p = wt[v] + edge.weight; if (p < wt[w]) { wt[w] = p; queue.lower(w); } } } } return wt; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyList setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); @Override AdjacencyList subgraph(int[] vertices); @Override SparseMatrix toMatrix(); static AdjacencyList of(SparseMatrix matrix); }
AdjacencyList implements Graph { @Override public double[] dijkstra(int s) { double[] wt = new double[n]; Arrays.fill(wt, Double.POSITIVE_INFINITY); PriorityQueue queue = new PriorityQueue(wt); for (int v = 0; v < n; v++) { queue.insert(v); } wt[s] = 0.0; queue.lower(s); while (!queue.empty()) { int v = queue.poll(); if (!Double.isInfinite(wt[v])) { for (Edge edge : graph[v]) { int w = edge.v2; if (!digraph && w == v) { w = edge.v1; } double p = wt[v] + edge.weight; if (p < wt[w]) { wt[w] = p; queue.lower(w); } } } } return wt; } AdjacencyList(int n); @SuppressWarnings("unchecked")  AdjacencyList(int n, boolean digraph); @Override int getNumVertices(); @Override boolean hasEdge(int source, int target); @Override double getWeight(int source, int target); @Override AdjacencyList setWeight(int source, int target, double weight); @Override Collection<Edge> getEdges(); @Override Collection<Edge> getEdges(int vertex); @Override Collection<Edge> getEdges(int source, int target); @Override Edge getEdge(int source, int target); @Override void addEdge(int source, int target); @Override void addEdge(int source, int target, double weight); @Override void removeEdges(Collection<Edge> edges); @Override void removeEdge(int source, int target); @Override void removeEdge(Edge edge); @Override int getDegree(int vertex); @Override int getIndegree(int vertex); @Override int getOutdegree(int vertex); @Override int[] sortdfs(); @Override int[][] dfs(); @Override void dfs(Visitor visitor); @Override int[] sortbfs(); @Override int[][] bfs(); @Override void bfs(Visitor visitor); @Override double[] dijkstra(int s); @Override AdjacencyList subgraph(int[] vertices); @Override SparseMatrix toMatrix(); static AdjacencyList of(SparseMatrix matrix);  }