Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //johnson
- #include<iostream>
- #include<fstream>
- #include<vector>
- #include<queue>
- #include<functional>
- #define INF 990
- using namespace std;
- typedef pair<int, int> p;
- vector<vector<int>> g;
- vector<int> dist;
- int n, m;
- void read()
- {
- ifstream in("file.txt");
- if (!in.is_open())
- cout << "error";
- else
- {
- in >> n >> m;
- g.resize(n + 1);
- for (int i = 0; i <= n; i++)
- g[i].assign(n + 1, 0);
- int x, y, w;
- dist.assign(n + 1, INF);
- for (int i = 0; i < m; i++)
- {
- in >> x >> y >> w;
- g[x][y] = w;
- }
- }
- }
- void change_matrix()
- {
- g.resize(n + 1);
- for (int i = 0; i <= n; i++)
- {
- g[0][i] = 0;
- g[i][0] = 0;
- }
- }
- bool belman(int source)
- {
- dist.assign(n + 1 , INF);
- dist[source] = 0;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for (int k = 1; k <= n; k++)
- if (dist[j] != INF)
- if(g[j][k]!=0 && dist[k]> dist[j]+g[j][k])
- dist[k] = dist[j] + g[j][k];
- //checking for negative cycles
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (g[i][j] != 0 && dist[i] > dist[j] + g[i][j])
- return false;
- return true;
- }
- void dijkstra(int source)
- {
- priority_queue <int, vector<int>, greater<int>> q;
- dist[source] = 0;
- q.push(source );
- while (!q.empty())
- {
- int i = q.top();
- q.pop();
- for (int j = 1; j <= n; j++)
- {
- if (g[i][j] != 0 && dist[i] > dist[j] + g[i][j])
- {
- dist[i] = dist[j] + g[i][j];
- q.push(j );
- }
- }
- }
- }
- void johnson(int source)
- {
- change_matrix();
- if (belman(source))
- {
- for (int i = 1; i < n; i++)
- for (int j = 1; j < n; j++)
- g[i][j] += dist[i] - dist[j];
- dist.assign(n + 1, INF);
- dist[source] = 0;
- dijkstra(source);
- }
- else
- cout << "contains negative cycles\n";
- }
- int main()
- {
- read();
- int source = 1;
- johnson(source);
- cout << "minimum distance between " << source << " and every node:\n";
- for (int i = 1; i < n; i++)
- cout << "node:" << i << " distance:" << dist[i] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement