Shortest Path Algorithms

    Bellman Ford's Algorithm:

    Time Complexity of Bellman Ford algorithm is relatively high O(V.E), in case E=V^2, O(V^3).
    Shortest path contains at most (N-1) edges, because the shortest path couldn't have a cycle.

    V- vertex
    E- Edge

    vector <int> v [V];
    int dis [V];

    for(int i = 0; i < V; i++){

        v[i].clear();
        dis[i] = 1e9;
    }

   for(int i = 0; i < E; i++){

        scanf("%d%d%d", &from , &next , &weight);

        v[i].push_back(from);
        v[i].push_back(next);
        v[i].push_back(weight);
   }

    dis[0] = 0;
    for(int i = 1; i <= V - 1; i++){
        for(int j=0;j<E;j++){

            if(dis[ v[j][0] ] + v[j][2] < dis[ v[j][1] ] ){
                dis[ v[j][1] ] = dis[ v[j][0]  ] + v[j][2];
            }
        }
    }


    Dijkstra's Algorithm:

    Time Complexity of Dijkstra's Algorithm is O(V^2) but with min-priority queue it drops down to O(V+ElogV) .

    #define SIZE 100000 + 1

    vector < pair < int , int > > v [SIZE];   // each vertex has all the connected vertices with the edges weights
    int dist [SIZE];
    bool vis [SIZE];

    void dijkstra(){
                                                    // set the vertices distances as infinity
        memset(vis, false , sizeof vis);            // set all vertex as unvisited
        dist[1] = 0;
        multiset < pair < int , int > > s;          // multiset do the job as a min-priority queue

        s.insert({0 , 1});                          // insert the source node with distance = 0

        while(!s.empty()){

            pair <int , int> p = *s.begin();        // pop the vertex with the minimum distance
            s.erase(s.begin());

            int x = p.s; int wei = p.f;
            if( vis[x] ) continue;                  // check if the popped vertex is visited before
             vis[x] = true;

            for(int i = 0; i < v[x].size(); i++){
                int e = v[x][i].f; int w = v[x][i].s;
                if(dist[x] + w < dist[e]  ){            // check if the next vertex distance could be minimized
                    dist[e] = dist[x] + w;
                    s.insert({dist[e],  e} );           // insert the next vertex with the updated distance
                }
            }
        }
    }

    However, if we have to find the shortest path between all pairs of vertices, both of the above methods would be expensive in terms of time.



    Floyd Warshall's Algorithm:

    Floyd\u2013Warshall's Algorithm is used to find the shortest paths between between all pairs of vertices in a graph, where each edge in the graph has a weight which is positive or negative. The biggest advantage of using this algorithm is that all the shortest distances between any  vertices could be calculated in V^3.

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
            }
        }
    }
    Time Complexity of FloydWarshall's Algorithm is V^3, where V is the number of vertices in a graph.