fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include <cstring>
  5. #include<climits>
  6.  
  7. using namespace std;
  8. int a[100][100], vs[100], n, d[100], truoc[100];
  9. int MAX = 999999;
  10.  
  11. void bellmanFord(int start){
  12.     d[start] = 0;
  13.     vs[start] = 1;
  14.     for (int i = 1; i <= n; i++) {
  15.         d[i] = a[start][i];
  16.         truoc[i] = start;
  17.         cout << d[i] << "|" << truoc[i] << " ";
  18.     }
  19.     cout << endl;
  20.  
  21.     int k = 1;
  22.     bool done = true;
  23.     while (k <= n-2) {
  24.         done = true;
  25.         for (int i = 1; i <= n; i++) {
  26.             for (int j = 1; j <= n; j++) {
  27.                 if (d[i] > d[j] + a[j][i]) {
  28.                     d[i] = d[j] + a[j][i];
  29.                     truoc[i] = j;
  30.                     done = false;
  31.                 }
  32.             }
  33.         }
  34.  
  35.         for (int i = 1; i <= n; i++) {
  36.             cout << d[i] << "|" << truoc[i] << " ";
  37.         }
  38.         cout << endl;
  39.         k++;
  40.     }
  41.     if (!done) cout << "Do thi co chu trinh am";
  42. }
  43.  
  44. int main() {
  45.     cout << "So dinh: ";
  46.     cin >> n;
  47.     // Khoi tao ma tran ke
  48.     cout << "Nhap ma tran:\n";
  49.     memset(vs, 0, sizeof(vs));
  50.  
  51.     for (int i = 1; i <= n; i++) {
  52.         for (int j = 1; j <= n; j++) {
  53.             cin >> a[i][j];
  54.             if (a[i][j] == 0 && i != j) a[i][j] = MAX;
  55.  
  56.         }
  57.     }
  58.     int start, goal;
  59.     cout << "Bat dau: ";
  60.     cin >> start;
  61.     bellmanFord(start);
  62.  
  63.  
  64.  
  65. }
  66.  
  67. /**
  68. Test:
  69.  
  70. 5
  71. 0 7 5 8 2
  72. 0 0 0 0 0
  73. 0 1 0 1 0
  74. 0 1 0 0 0
  75. 0 0 0 1 0
  76.  
  77. 4
  78. 0 4 3 0
  79. 0 0 -2 0
  80. 0 0 0 2
  81. -1 0 0 0
  82.  
  83. **/
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
So dinh: Nhap ma tran:
Bat dau:
https://ideone.com/qhLB22
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!