35 lines
1.2 KiB
Java
35 lines
1.2 KiB
Java
// You have a graph G (original graph), with edge weight values v(u->w)
|
|
// You must call this function with a helper graph with a special node
|
|
// indexed 0 and zero-weight edges 0->w for all vertices w
|
|
// Time complexity: O(N^2 * lg N + N*#Edges)
|
|
// Returns APSP indexed as expected in the original graph (i.e.,
|
|
// shifting everything -1 to exclude the special node of the helper graph)
|
|
private static int[][]
|
|
int_johnson (DirectedWeightedGraph<Integer> hg) throws Exception
|
|
{
|
|
// Finish the helper graph by running Bellman-Ford on it
|
|
int[] h = hg.int_bellman_ford(0);
|
|
|
|
// Generate the tweaked graph
|
|
for (int u = 1; u < hg.n_nodes; ++u) {
|
|
hg.edges(u).forEach((w) -> {
|
|
int edge_cost = (int) hg.weight(u, w).get(0);
|
|
// Update edge's cost
|
|
hg.link(u, w, edge_cost + h[u] - h[w]);
|
|
}
|
|
}
|
|
|
|
int [][] D = new int[hg.n_nodes-1][hg.n_nodes-1];
|
|
|
|
// Dijkstra on the tweaked graph
|
|
for (int u = 0; u < g.n_nodes-1; ++u) {
|
|
for (int w = 0; w < g.n_nodes-1; ++w) {
|
|
int[] delta = hg.int_dijkstra(u+1);
|
|
D[u][w] = delta[w+1] + h[w+1] - h[u+1];
|
|
}
|
|
}
|
|
|
|
// Johnson drops mic.
|
|
return D;
|
|
}
|