Jhonson
Introduction:
This algorithm gives shortest paths from every vertex to every other vertex using two algorithms Bellman ford and Dijkstra's shortest path algorithm
Problem Statement:
print the shortest paths from every vertex to every other vertex.
Algorithm
1. Adding a dummy new node \(q\) with zero-weighted edges to all other vertices.
2. Run \(bellman\_ford(G, q)\) and let the shortest paths be put in array \(h[\ ]\). Terminate if negative weighted cycle is detected.
3. Change the weights of edges in original graph by adding \(h[u]-h[v]\) to \(weight(u, v)\)
4. Remove vertex q and its edges with other vertices.
5. Run dijkstra for every vertex to find shortest path from every vertex to every other vertex.(stored into a 2D |V|x|V| matrix)
6. Add \(h[v]-h[u]\) to all path weights in 2D matrix.
Code :
// shortest path between every pair of vertices
// O(v^2logV + VE)
// uses both dijkstra and Bellman ford
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
#define adjacency_list map<int, vector<pair<int, int>>>
#define mp make_pair
#define INF INT_MAX
typedef struct edge
{
int u;
int v;
int w;
} Edge;
typedef struct graph
{
adjacency_list adj;
int num_edges;
int num_vertices;
vector<Edge> edge;
} graph;
bool bellmanford(graph G, int source, vector<int> &dist)
{
set<int> vertex_set;
for (int i = 0; i < G.num_vertices; i++)
{
vertex_set.insert(i);
}
// cout << "bell--\n";
// main part of algorithm
dist[source] = 0;
for (int i = 0; i < G.num_vertices - 1; i++)
{
for (int j = 0; j < G.num_edges; j++)
{
int u = G.edge[j].u;
int v = G.edge[j].v;
int w = G.edge[j].w;
if (dist[u] != INF && dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
}
}
}
// for (int i = 0; i < G.num_vertices; i++)
// {
// cout << dist[i] << "\n";
// }
// cout << "bell--\n";
//// cycle detection
for (int j = 0; j < G.num_edges; j++)
{
int u = G.edge[j].u;
int v = G.edge[j].v;
int w = G.edge[j].w;
if (dist[u] != INF && dist[u] + w < dist[v])
{
return false;
}
}
return true;
}
void dijkstra(graph G, int dist[], int source)
{
set<int> vertex_set;
for (int i = 0; i < G.num_vertices; i++)
{
vertex_set.insert(i);
}
dist[source] = 0;
while (!vertex_set.empty())
{
int u = *(vertex_set.begin()); // if these two lines are not initialised then we may end up looping on single vertex
int min_dist = dist[u];
for (auto i : vertex_set)
{
if (dist[i] < min_dist)
{
u = i;
min_dist = dist[i];
}
}
vertex_set.erase(u);
// u has vertex with min distance from source
// terminate dijkstra if you want min ditance to this vertex.
for (auto e : G.edge)
{
if (e.u == u)
{
if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
{
dist[e.v] = dist[e.u] + e.w;
}
}
}
// for (auto i : G.adj[u])
// {
// int v = i.first;
// int new_dist = dist[u] + i.second;
// if (new_dist < dist[v])
// {
// dist[v] = new_dist;
// }
// }
// cout << u << "\n";
// sleep(1);
}
// for (int i = 0; i < G.num_vertices; i++)
// {
// cout << dist[i] << " ";
// }
// cout << "\n";
}
void johnson(graph G)
{
// creating a new graph with new node q connected all other nodes wih 0 weighted edge
int new_node = G.num_vertices;
int orignal_num_edges = G.num_edges;
G.num_edges += G.num_vertices;
G.num_vertices++;
for (int i = orignal_num_edges; i < G.num_edges; i++)
{
G.edge.push_back(Edge{new_node, i - orignal_num_edges, 0});
}
// for (auto i : G.edge)
// {
// cout << i.u << " " << i.v << " " << i.w << "\n";
// }
// bellman ford part of algorithm
// cout << "bellman ford--\n";
vector<int> h(G.num_vertices, INF);
if (!bellmanford(G, new_node, h))
{
cout << "negative edge cycle detected...\nexiting....\n";
return;
}
// reweighing the edges
// cout << "reweighting edges--\n";
for (int i = 0; i < orignal_num_edges; i++)
{
G.edge[i].w += h[G.edge[i].u] - h[G.edge[i].v];
}
// remove new_edge
// cout << "removing edges--\n";
G.num_vertices--;
G.num_edges = orignal_num_edges;
// for (auto i : G.edge)
// {
// cout << i.u << " " << i.v << " " << i.w << "\n";
// }
for (int i = 0; i < G.num_vertices; i++)
{
G.edge.pop_back();
}
// dijkstra
// cout << "removed edges\n";
// for (auto i : G.edge)
// {
// cout << i.u << " " << i.v << " " << i.w << "\n";
// }
// cout << "dijkstra--\n";
int dist[G.num_vertices][G.num_vertices];
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
dist[i][j] = INF;
}
}
for (int i = 0; i < G.num_vertices; i++)
{
dijkstra(G, &dist[i][0], i);
// cout << "i = " << i << "\n--------------------\n";
}
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
dist[i][j] += h[j] - h[i];
}
}
for (int i = 0; i < G.num_vertices; i++)
{
for (int j = 0; j < G.num_vertices; j++)
{
if (dist[i][j] == INF)
{
cout << "INF ";
}
else
{
printf("%-4d ", dist[i][j]);
}
}
cout << "\n";
}
}
int main()
{
// undirected graph
graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
cin >> G.num_vertices;
cin >> G.num_edges;
int u, v, w;
for (int i = 0; i < G.num_edges; i++)
{
cin >> u >> v >> w;
G.edge.push_back(Edge{u, v, w});
}
johnson(G);
// cout << "\n";
}
Complexity Analysis :
Time complexity : \(O(|V|.|E| + |V|(dijkstra\_complexity))\)
Time complexity (normal dijkstra without min-heaps or fibonacci heaps): \(O(|V|.|E| + |V|^3)\) ≈ \(O(|V|^3)\)
Time complexity ( dijkstra with min-heaps or fibonacci heaps): \(O(|V|.|E| + |V|^2log|V|)\) which is better than Floyd warshall.