floyds.cpp File Reference

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>

Functions
template<typename Assoc_Cont >
Assoc_Cont &	floyds_sp (WeightedGraph &G)
int	main ()

Function Documentation

template<typename Assoc_Cont >

Assoc_Cont& floyds_sp

(

WeightedGraph &

G

)

                                        {

    // !! Requires a container of that maps pair of vertices to an int as the temp-arg.
    
    Assoc_Cont& path_wt = *(new Assoc_Cont);
    
    int V = G.no_of_vertices();
    
    // Initialize the matrix
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            if(i == j)
                path_wt[i][i] = 0;
            else if(G.weight(i, j) != -1)
                path_wt[i][j] = G.weight(i, j);
            else
                path_wt[i][j] = INF;
        }
    }
    
    vector<int> vertex_set(V);
    G.get_vertices(vertex_set.begin());
    
    for(int pivot : vertex_set) {
        // Relax all the paths that go through the pivot    
        
        for(int from : vertex_set)
            for(int to : vertex_set)
                if(path_wt[from][to] > path_wt[from][pivot] + path_wt[pivot][to])
                    path_wt[from][to] = path_wt[from][pivot] + path_wt[pivot][to];
    
    }
    
    return path_wt;     
}

int main

(

)

           {
    WeightedGraph G(4);
    G.add_edge(0, 1, 2);
    G.add_edge(1, 2, 4);
    G.add_edge(2, 3, 1);
    G.add_edge(2, 6, 6);
    G.add_edge(3, 0, 3);
    
    map<int, map<int, int>> path_wt;
    
    path_wt = floyds_sp<map<int, map<int, int>>>(G);
    
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++)
            cout << path_wt[i][j] << "\t";
        cout << endl;
    }
    
}