Floyed Warshal

Floyed Warshal is a classical graph algorithm. The Floyed Warshal algorithm assumes that the graph contains no negative cycles but if the graph has negative cycles the algorithm can still detect them. The Floyed Warshal algorithm is used to find all shortest paths. This algorithm works in O(n^3).

C++ code

#include <iostream>
#include <vector>
using namespace std;
const int INF=500*1000;
int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n,a;
   cin >> n >> a;
   vector<vector<int>> adj(n+1,vector<int> (n+1));
   // input reading
   for (int i=0; i<a; ++i){

      int inter1,inter2,dist;

      cin >> inter1 >> inter2 >> dist;
      adj[inter1][inter2] = dist;
      adj[inter2][inter1] = dist;
   }
   // initialisation
   vector<vector<int>> distance(n+1,vector<int> (n+1,INF));
   for (int i=1; i<=n; ++i){
      distance[i][i] = 0;
      for (int j=1; j<=n; ++j){
         if (adj[i][j]) distance[i][j] = adj[i][j];
      }
   }
   // Floyed Warshal algorithm
   for (int k=1; k<=n; ++k){
      for (int i=1; i<=n; ++i){
         for (int j=1; j<=n; ++j){
            distance[i][j] = min(distance[i][j],distance[i][k]+distance[k][j]);
         }
      }
   }
   // printing
   for (int i=1; i<=n; ++i){
      bool first=true;
      for (int j=1; j<=n; ++j){
         if (!first) cout << ' ';
         first = false;
         cout << distance[i][j];
      }
      cout << '\n';
   } 
   return 0;
}

I have found a alternative, it is a bit slower then Floyed - Warshal's algorithm (if you don't want to do Floyed Warshal). The idea of the alternative is to do a adjacent matrix and then perform n times Dijkstra's algorithm.