Floyd.cpp

#include<iostream>
#include<cstdio>

using namespace std;

void addEdge(int source,int target,int weight);

void Floyd();

int w(int source,int target);

void relax(int source,int target);

int graph[5][5];

int main(){

    //initialize
    for(int i=0;i<=4;i++){
        for(int j=0;j<=4;j++){
            graph[i][j]=9999;
        }
    }
    for(int i=0;i<=4;i++) graph[i][i]=0;

    //add edge, run floyd method
    addEdge(0,1,2);
    addEdge(1,2,20);
    addEdge(2,3,1);
    addEdge(0,3,5);
    addEdge(3,4,1);

    Floyd();
    //output
    for(int i=0;i<=4;i++)
    {
        for(int j=0;j<=4;j++) printf("%5d",graph[i][j]);
        cout<<endl;
    }
}

void addEdge(int source,int target,int weight){
    graph[source][target]=weight;
    graph[target][source]=weight;
}
int w(int source,int target){
    return graph[source][target];
}

void relax(int source,int target){
    if(graph[source][source]+w(source,target)<graph[target][target]){
        graph[target][target]=w(source,target)+graph[source][source];
    }
}

void Floyd(){
    for(int k=0;k<=4;k++){
        for(int i=0;i<=4;i++){
            for(int j=0;j<=4;j++){
                if(graph[i][k]+graph[k][j]<graph[i][j]){
                    graph[i][j]=graph[i][k]+graph[k][j];
                }
            }
        }
    }
}