Bellman-Ford
A. First Edition
This is just a small assignment from networking and the assignment is a theory one. But I am so lazy to do the
numb-minded-mechanical job that I would rather my best friend, my laptop, to do it for me.
Bellman-Ford is said to be a distributed algorithm for routing algorithm. The question is just how the nodes in
a network find out the cheapest route to each other node. Considering the graph is an undirected graph with each
vertex representing a router and with each edge attached with an integer cost. The bigger the cost is, the
slower for the transmission would pass through the edge.
C.The idea of programI use adjacency matrix to represent the graph with each entry as the cost. If two vertices are not adjacent, the
cost is "INFINITE" which is just -1. The following is the input matrix. However, at last I changed the
"INFINITE" in routing matrix to be 1000.
0 3 -1 3 -1 -1 -1
3 0 2 -1 -1 -1 -1
-1 2 0 2 2 -1 -1
3 -1 2 0 6 -1 -1
-1 -1 2 6 0 4 3
-1 -1 -1 -1 4 0 -1
-1 -1 -1 -1 3 -1 0
The logic of Bellman-Ford algorithm is rather intuitive and simple. It is like people's exchanging information.
i.e. People go to pub and talk and exchange information and compare with his old knowledge. When he find a new
route, he updates his routing table. However, read the graph is a bit boring, so, I borrow my old code---matrix
which already implement the "readFromFile" function.
I add a small "update" function which will go through the new-found path and update the cost of each node in the path if possible.
Here, I mean to update when the original cost is bigger than current. I am not sure about the original algorithm. Probably it won't
bother to do this. Because it is much easy for man to observe the graph.
E.Further improvement
F.File listing
1. matrix.h
1. matrix.cpp
1. BellmanFord.cpp
file name: matrix.h
#ifndef MATRIX_H
#define MATRIX_H
const int MaxRow = 10;
const int MaxCol = 10;
const double LIMIT = 0.01;
class Matrix
{
private:
int rowNum;
int colNum;
double lst[MaxRow][MaxCol];
protected:
void mul(int dest, double scalor);
void mul(int source, int dest, double scalor);
public:
Matrix();
Matrix& transform(int index1, int index2);
int row() const {return rowNum;}
int col() const {return colNum;}
void setRow(const int newRow) { rowNum = newRow;}
void setCol(const int newCol) { colNum = newCol;}
void display(bool displayNumber= false);
double& items(int r, int c);
void initialize();
void readFromFile(const char* fileName);
void assign(const Matrix& other);
Matrix& operator = (Matrix& other);
Matrix& transposition();
bool operator==(Matrix& other);
bool operator!=(Matrix& other);
double* operator[](int r);
};
#endif
file name: matrix.cpp
#include <iostream>
#include <cmath>
#include <fstream>
#include "matrix.h"
using namespace std;
double* Matrix::operator [](int r)
{
return lst[r];
}
Matrix& Matrix::transposition()
{
double hold;
int temp;
for (int r =0; r< rowNum; r++)
{
for (int c=0; c< r; c++)
{
hold = lst[r][c];
lst[r][c] = lst[c][r];
lst[c][r] = hold;
}
}
temp = rowNum;
rowNum = colNum;
colNum = temp;
return (*this);
}
bool Matrix::operator==(Matrix& other)
{
if (row()!=other.row()||col()!=other.col())
{
return false;
}
for (int r=0; r<row(); r++)
{
for (int c=0; c<col(); c++)
{
if (items(r,c)!=other.items(r,c))
{
return false;
}
}
}
return true;
}
bool Matrix::operator !=(Matrix& other)
{
return !(this->operator ==(other));
}
Matrix& Matrix::operator =(Matrix& other)
{
setRow(other.row());
setCol(other.col());
for (int r=0; r< other.row(); r++)
{
for (int c=0; c< other.col(); c++)
{
lst[r][c] = other.items(r, c);
}
}
return (*this);
}
void Matrix::assign(const Matrix& other)
{
this->operator =((Matrix&)other);
}
void Matrix::mul(int dest, double scalor)
{
for (int c=0; c< colNum; c++)
{
lst[dest][c] *= scalor;
}
}
void Matrix::mul(int source, int dest, double scalor)
{
for (int c=0; c< colNum; c++)
{
lst[dest][c] += lst[source][c]*scalor;
}
}
double& Matrix::items(int r, int c)
{
return lst[r][c];
}
void Matrix::readFromFile(const char* fileName)
{
int r=0, c=0;
char ch;
ifstream f;
f.open(fileName);
while (!f.eof())
{
ch = f.peek();
if (ch!=10) //return char
{
f>>lst[r][c];
c++;
if (c>colNum)
colNum = c;
}
else
{
f.ignore();
r++;
setCol(c);
c =0;
}
}
if (r!=0)
{
setRow(r+1);
}
}
void Matrix::initialize()
{
for (int r=0; r < rowNum; r++)
{
for (int c=0; c< colNum; c++)
{
lst[r][c] = r*2+c;
}
}
}
Matrix& Matrix::transform(int index1, int index2)
{
double hold;
if (index1<rowNum&&index2<rowNum)
{
for (int i=0; i<colNum; i++)
{
hold = lst[index1][i];
lst[index1][i] = lst[index2][i];
lst[index2][i] = hold;
}
for (i=0; i< rowNum; i++)
{
hold = lst[i][index1];
lst[i][index1] = lst[i][index2];
lst[i][index2] = hold;
}
}
return *this;
}
void Matrix::display(bool displayNumber)
{
// int temp;
long preFlag;
int number=0;
preFlag = cout.flags();
// temp = cout.precision(4);
// cout.setf(ios::fixed);
cout<<"\nrow\\col";
for (int c=0; c< colNum; c++)
{
cout<<" "<<c;
}
cout<<"\n\n";
for (int r = 0; r< rowNum; r++)
{
cout<<r<<"\t ";
number = 0;
for (c = 0; c< colNum; c++)
{
cout<<(fabs(lst[r][c])<LIMIT?0:lst[r][c])<<" ";
if (fabs(lst[r][c])>=LIMIT)
{
number++;
}
}
if (displayNumber)
{
cout<<number;
}
cout<<endl;
}
// cout.precision(temp);
cout.flags(preFlag);
}
Matrix::Matrix()
{
rowNum = 5;
colNum = 5;
initialize();
}
file name: BellmanFord.cpp
#include <stdio.h>
#include <stdlib.h>
#include "matrix.h"
const int MaxVertex=10;
const int INFINITE=1000;
struct Node
{
int index;
int cost;
};
class Bellman
{
private:
Matrix matrix;
Node nodeMatrix[MaxVertex][MaxVertex];
int row, col;
void update(int r, int c, int first);
public:
void readFile(char* fileName);
void display();
void displayMatrix();
bool findCost(int r, int c);
void doFindCost();
};
int main()
{
Bellman B;
B.readFile("nick.txt");
B.display();
B.doFindCost();
//B.displayMatrix();
B.display();
return 0;
}
void Bellman::doFindCost()
{
bool findNew;
do
{
findNew=false;
for (int r=0; r<row; r++)
{
for (int c=0; c<col; c++)
{
if (findCost(r, c))
{
//display();
printf("array[%d][%d]\n", r, c);
findNew=true;
}
}
display();
}
}
while (findNew);
}
bool Bellman::findCost(int r, int c)
{
bool findNew=false;
int oldCost=nodeMatrix[r][c].cost;
int newCost, theRow;//, theCol;
for (int i=0; i<col; i++)
{
//HAVE A PATH
newCost=nodeMatrix[r][i].cost;
//theCol=
theRow=r;
while ((theRow=nodeMatrix[theRow][i].index)!=INFINITE)
{
//newCost += nodeMatrix[theRow][i].cost;
if (i==theRow)
{
newCost=nodeMatrix[r][i].cost+nodeMatrix[theRow][c].cost;
if (newCost<oldCost)
{
nodeMatrix[r][c].cost=newCost;
oldCost=newCost;
nodeMatrix[r][c].index=nodeMatrix[r][i].index;
update(r, c, i);
findNew=true;
}
break;
}
}
}
return findNew;
}
void Bellman::update(int r, int c, int first)
{
int newCost, theRow;
newCost=nodeMatrix[r][c].cost;
theRow=r;
while ((theRow=nodeMatrix[theRow][first].index)!=first)
{
if (newCost-nodeMatrix[r][theRow].cost>0)
{
if (nodeMatrix[theRow][c].cost>newCost-nodeMatrix[r][theRow].cost)
{
nodeMatrix[theRow][c].index=nodeMatrix[theRow][first].index;
nodeMatrix[theRow][c].cost=newCost-nodeMatrix[r][theRow].cost;
}
}
}
}
void Bellman::readFile(char* fileName)
{
matrix.readFromFile(fileName);
row=matrix.row();
col=matrix.col();
for (int r=0; r<row; r++)
{
for (int c=0; c<col; c++)
{
if (matrix[r][c]>0)
{
nodeMatrix[r][c].index=c;
nodeMatrix[r][c].cost=(int)matrix[r][c];
}
else
{
if (matrix[r][c]==0)
{
nodeMatrix[r][c].index=r;
nodeMatrix[r][c].cost=0;
}
else
{
nodeMatrix[r][c].index=INFINITE;
nodeMatrix[r][c].cost=INFINITE;
}
}
}
}
}
void Bellman::display()
{
for (int i=0; i<row; i++)
{
printf("\t%c", i+'A');
}
printf("\n------------------------------\n");
for (int r=0; r<row; r++)
{
printf("%c\t", r+'A');
for (int c=0; c<col; c++)
{
if (nodeMatrix[r][c].index!=INFINITE)
{
printf("(%c,%d)\t", nodeMatrix[r][c].index+'A', nodeMatrix[r][c].cost);
}
else
{
printf("(-,-)\t");
}
}
printf("\n");
}
}
void Bellman::displayMatrix()
{
matrix.display();
}
How to run?
1. You need the graph input matrix file---"nick.txt" which is like following:
0 3 -1 3 -1 -1 -1
3 0 2 -1 -1 -1 -1
-1 2 0 2 2 -1 -1
3 -1 2 0 6 -1 -1
-1 -1 2 6 0 4 3
-1 -1 -1 -1 4 0 -1
-1 -1 -1 -1 3 -1 0
2. I give two output version: one is a debug-version which shows each iteration the matrix discover new route;
the other is just the start and end matrix.
3. This the final clean output version:
A B C D E F G
------------------------------
A (A,0) (B,3) (-,-) (D,3) (-,-) (-,-) (-,-)
B (A,3) (B,0) (C,2) (-,-) (-,-) (-,-) (-,-)
C (-,-) (B,2) (C,0) (D,2) (E,2) (-,-) (-,-)
D (A,3) (-,-) (C,2) (D,0) (E,6) (-,-) (-,-)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (D,11) (D,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
4. The debug-version output:
A B C D E F G
------------------------------
A (A,0) (B,3) (-,-) (D,3) (-,-) (-,-) (-,-)
B (A,3) (B,0) (C,2) (-,-) (-,-) (-,-) (-,-)
C (-,-) (B,2) (C,0) (D,2) (E,2) (-,-) (-,-)
D (A,3) (-,-) (C,2) (D,0) (E,6) (-,-) (-,-)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[0][2]
array[0][4]
array[0][5]
array[0][6]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (-,-) (C,4) (C,8) (C,7)
C (-,-) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (-,-) (C,2) (D,0) (E,6) (-,-) (-,-)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[1][3]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (-,-) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (-,-) (C,2) (D,0) (E,6) (-,-) (-,-)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[2][0]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (-,-) (C,2) (D,0) (E,6) (-,-) (-,-)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[3][1]
array[3][4]
array[3][5]
array[3][6]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (-,-) (-,-) (C,2) (D,6) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[4][0]
array[4][1]
array[4][3]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (-,-) (-,-) (-,-) (-,-) (E,4) (F,0) (-,-)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[5][0]
array[5][1]
array[5][2]
array[5][3]
array[5][6]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (-,-) (-,-) (-,-) (-,-) (E,3) (-,-) (G,0)
array[6][0]
array[6][1]
array[6][2]
array[6][3]
array[6][5]
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
A B C D E F G
------------------------------
A (A,0) (B,3) (B,5) (D,3) (B,7) (B,11) (B,10)
B (A,3) (B,0) (C,2) (C,4) (C,4) (C,8) (C,7)
C (B,5) (B,2) (C,0) (D,2) (E,2) (E,6) (E,5)
D (A,3) (C,4) (C,2) (D,0) (C,4) (C,8) (C,7)
E (C,7) (C,4) (C,2) (C,4) (E,0) (F,4) (G,3)
F (E,11) (E,8) (E,6) (E,8) (E,4) (F,0) (E,7)
G (E,10) (E,7) (E,5) (E,7) (E,3) (E,7) (G,0)
Press any key to continue