Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_V = 101; int V; vector<pair<int, int> > G[MAX_V]; vector<int> bellman_ford(int start) { vector<int> distances; distances.resize(V); for (int i=0; i < V; i++) { distances[i] = 1000000000; } distances[start] = 0; for (int iteration=0; iteration <= V + 1; iteration++) { bool distances_change = false; for (int j=0; j<V; j++) { for (auto edge : G[j]) { int from = j; int to = edge.first; int weight = edge.second; if (distances[to] > distances[from] + weight) { distances[to] = distances[from] + weight; distances_change = true; } } } if (distances_change == false) { //nema potreba da prodolzhime, bidejki nemashe //promena na rastojanijata vo prethodnata iteracija break; } else { if (iteration == (V + 1)) { cout << "Error. Negative-weight cycle." << endl; } } } return distances; } int main() { cout << "Number of cities: " << endl; cin >> V; int E; cout << "Number of connections: " << endl; cin >> E; cout << "Enter the edges (from, to, weight)..." << endl; for (int i=0; i<E; i++) { int from, to, weight; cin >> from >> to >> weight; G[from].push_back({to, weight}); } int start; cout << "What's the start city: " << endl; cin >> start; vector<int> distances = bellman_ford(start); for (int i=0; i<V; i++) { cout << "distance to city " << i << " is " << distances[i] << endl; } return 0; }
Input data
Program output
3 3 0 1 10 0 2 20 1 2 5 0
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!