Bellman-Ford.cpp

#include<iostream>
#include<cstdio>

using namespace std;

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

void BellmanFord();

int w(int source,int target);

void relax(int source,int target);

int graph[5][5]={0};

int main(){

    //initialize
    graph[0][0]=0;
    for(int i=1;i<=4;i++) graph[i][i]=9999;
    
    //add edge, run bellmanford method
    addEdge(0,1,2);
    addEdge(1,2,5);
    addEdge(2,3,1);
    addEdge(0,3,2);
    addEdge(3,4,1);
    for(int i=0;i<=4;i++)
    {
        for(int j=0;j<=4;j++) printf("%5d",graph[i][j]);
        cout<<endl;
    }
    BellmanFord();
    //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;
}
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 BellmanFord(){
    //run graph numbers times
    for(int i=0;i<=4;i++){
        //relax graph G
        for(int j=0;j<=4;j++)
        {
            for(int k=0;k<=4;k++)
            {
                if(w(j,k)!=0) relax(j,k);
            }
        }
    }
}