Function johnson

Algorithms/JohnsonAlgorithm.cpp:132–195

}

int johnson(int t_no, int n, int m) {

	// step 1: create a new vertex (0) and add edge from it to all other vertices
	for (int i = 1; i <= n; i ++) {
		edges.push_back({0, {i, 0}});
	}

	// step 2: run bellman ford with (0) as the source
	vector <int> h(n + 1, INT_MAX);
	h[0] = 0;
	bool negative_cycle = bellman_ford(0, n + 1, m + n, h);
	if (negative_cycle) {
		return 0;
	}
	else {
		cout << "graph " << t_no + 1 << " ";
		cout << "yes" << endl << endl;

		// print the h_vector
		for (int i = 1; i <= n; i ++) {
			cout << h[i] << " ";
		}
		cout << "0"; // h(n + 1), i.e. new vertex
		cout << endl << endl;
	}

	// step 3: reweight all the edges of the original graph
	// wt'(u, v) = wt(u, v) + h[u] - h[v]

	for (int i = 0; i < m; i ++) {
		pair <int, pair <int, int> > edge;
		edge = edges[i];
		int first_node = edge.first;
		int second_node = edge.second.first;
		int weight = edge.second.second;
		weight += h[first_node] - h[second_node];
		adj_new[first_node].push_back({second_node, weight});
	}

	// step 4: run dijkstra's algo for all the vertices 1 to n
	// in the graph formed by adj_new

	vector <vector <int> > all_pair_dist;
	vector <int> cur_dist;
	for (int i = 1; i <= n; i ++) {
		cur_dist.assign(n + 1, INT_MAX);
		dijkstra(i, n, m, cur_dist, h);
		all_pair_dist.push_back(cur_dist);
	}

	// print the all-pair shortest paths
	for (int i = 0; i < n; i ++) {
		for (int j = 1; j <= n; j ++) {
			if (all_pair_dist[i][j] != INT_MAX) {
				cout << all_pair_dist[i][j] << " ";
			}
			else {
				cout << "# ";