Dijkstra ----Shortest Path
A.First Edition
This is actually first edition of my Dijkstra class which is a standard algorithm for finding shortest path.
It is a kind of interpretation from the algorithm of text.
This can be called 1.5 edition, as I corrected the bug in display method.
A simple connected graph with weighted edges which stands for distance between the two incident vertices. Starting
from one vertex and ends at one vertex, what is the shortest distance and what is the path?
I use my matrix class to store the weight graph with 1000 standing for no direct connection of two vertices. A
boolean array to stand for the set S. And a structure Label to store "label number, previous vertex, and step".
The problem of previous edition is that I didn't really understand the algorithm. The only way to backtrack the
path is by way of its previous vertex from the end point till start point. That is why we need a structure Label
to keep record both label number and its "Father".
1. void Dijkstra::doFindPath()
The method findNext is finding all elements not in setList and has the minimum label number.
2. void Dijkstra::display()
In C++, it is a pity that we don't have stack like assembly. I have to make it myself when backtracking the path.
3.void Dijkstra::updateVertex()
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
const int MaxElements = 20;
const int MaxRow = 20;
const int MaxCol = 20;
const double LIMIT = 0.01;
const int Infinite = 1000;
char* nameString[11] = {"a","b","c","d","e","f","g","h","i","j","k"};
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();
};
struct Label
{
int labelNum;
int father;
int step;
};
class Dijkstra
{
private:
bool setList[MaxElements];
int elementCount;
int startIndex;
int endIndex;
Matrix weight;
Label opMatrix[MaxElements];
int current;
int domino; //the u
void initialize();
void display();
bool isEnd() { return setList[endIndex];}
void doFindPath();
int findMin();
bool findNext();
void updateVertex();
int step;
void addElement();
public:
void findPath(int start, int end);
};
int main()
{
Dijkstra D;
D.findPath(0, 10);
return 0;
}
//as we cannot know how many step from start to end, I have to make
//a stack to record the step backwards.
void Dijkstra::display()
{
int stack[MaxElements] = {0};
int counter =0;
cout<<"The shortest distance is:"<<opMatrix[endIndex].labelNum<<endl;
cout<<"The path is:\n";
step = endIndex;
stack[counter] = step;
while (step!=startIndex)
{
step = opMatrix[step].father;
counter++;
stack[counter] = step;
}
for (int i=counter; i>=0; i--)
{
cout<<"step "<<counter -i + 1<<" is "<<nameString[stack[i]]<<endl;
cout<<"and its label is"<<opMatrix[stack[i]].labelNum<<endl;
}
}
void Dijkstra::addElement()
{
setList[domino] = true; //add domino to set
opMatrix[domino].step = step;
step++;
}
bool Dijkstra::findNext()
{
for (int i=current+1;i<elementCount; i++)
{
if (!setList[i] && weight.items(domino, i)!=Infinite)
{
current=i;
return true;
}
}
current = -1;
return false;
}
void Dijkstra::updateVertex()
{
if (opMatrix[domino].labelNum + weight.items(domino, current)<opMatrix[current].labelNum)
{
opMatrix[current].labelNum = opMatrix[domino].labelNum + weight.items(domino, current);
opMatrix[current].father = domino;
}
}
int Dijkstra::findMin()
{
int result = Infinite;
int index = 0;
for (int i=0; i< elementCount; i++)
{
if (!setList[i]) //not in set
{
if (opMatrix[i].labelNum<result)
{
result = opMatrix[i].labelNum;
index = i;
}
}
}
return index;
}
void Dijkstra::doFindPath()
{
while (!isEnd())
{
domino = findMin();
addElement();
while (findNext())
{
updateVertex();
}
}
}
void Dijkstra::findPath(int start, int end)
{
startIndex = start;
endIndex = end;
initialize();
weight.display();
doFindPath();
display();
}
void Dijkstra::initialize()
{
weight.readFromFile("c:\\nickGraph.txt");
elementCount = weight.row();
for (int i=0; i<elementCount; i++)
{
setList[i] = false;
opMatrix[i].labelNum = Infinite;
opMatrix[i].father = startIndex;
opMatrix[i].step = step;
}
opMatrix[startIndex].labelNum = 0;
current = -1;
step=0;
}
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);
}
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 = 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();
}
The following is result of program:
This is the first result that starts from "a" or index 0, and ends at "z" or index 5, it has exactly same result from text.
row\col 0 1 2 3 4 5 0 1000 4 2 1000 1000 1000 1 4 1000 1 5 1000 1000 2 2 1 1000 8 10 1000 3 1000 5 8 1000 2 6 4 1000 1000 10 2 1000 3 5 1000 1000 1000 6 3 1000 The shortest distance is:13 The path is: step 1 is a its last step isa and its label is0 step 2 is c its last step isa and its label is2 step 3 is b its last step isc and its label is3 step 4 is d its last step isb and its label is8 step 5 is e its last step isd and its label is10 step 6 is z its last step ise and its label is13
This is quite annoying! I try to test it by choosing starting vertex as "e" or index 4 which is adjacent to ending vertex "z" or
index of 5. It is giving correct distance, but with incorrect path! Originally I thought it should be e-->z, but it actually goes
to d first as e->d is shorter. After that it gives correct label of "z", but the path is just incorrect!
row\col 0 1 2 3 4 5 0 1000 4 2 1000 1000 1000 1 4 1000 1 5 1000 1000 2 2 1 1000 8 10 1000 3 1000 5 8 1000 2 6 4 1000 1000 10 2 1000 3 5 1000 1000 1000 6 3 1000 The shortest distance is:3 The path is: step 1 is e its last step ise and its label is0 step 2 is d its last step ise and its label is2 step 3 is z its last step ise and its label is3
The above is first edition result, now it is correct after I made correction in
display method.
This is starting from vertex "a"
row\col 0 1 2 3 4 5 0 1000 4 2 1000 1000 1000 1 4 1000 1 5 1000 1000 2 2 1 1000 8 10 1000 3 1000 5 8 1000 2 6 4 1000 1000 10 2 1000 3 5 1000 1000 1000 6 3 1000 The shortest distance is:13 The path is: step 1 is a and its label is0 step 2 is c and its label is2 step 3 is b and its label is3 step 4 is d and its label is8 step 5 is e and its label is10 step 6 is z and its label is13 Press any key to continue
this is starting from vertex "e" which is adjacent to target "z".
row\col 0 1 2 3 4 5 0 1000 4 2 1000 1000 1000 1 4 1000 1 5 1000 1000 2 2 1 1000 8 10 1000 3 1000 5 8 1000 2 6 4 1000 1000 10 2 1000 3 5 1000 1000 1000 6 3 1000 The shortest distance is:3 The path is: step 1 is e and its label is0 step 2 is z and its label is3 Press any key to continue
And here is the input weight matrix:( The 1000 stands for not directly connected, and the matrix is adjacent vertex Matrix.)
1000 4 2 1000 1000 1000 4 1000 1 5 1000 1000 2 1 1000 8 10 1000 1000 5 8 1000 2 6 1000 1000 10 2 1000 3 1000 1000 1000 6 3 1000
This is the running result of my assignment:
row\col 0 1 2 3 4 5 6 7 8 9 10
0 1000 1 3 10 10 5 1000 1000 1000 1000 1000
1 1 1000 1000 1000 7 1000 1000 1000 1000 1000 1000
2 3 1000 1000 1000 1000 1 1000 1000 1000 1000 1000
3 10 1000 1000 1000 2 5 8 4 6 1000 1000
4 10 7 1000 2 1000 1000 1000 8 1000 1000 1000
5 5 1000 1 5 1000 1000 1000 1000 10 1000 1000
6 1000 1000 1000 8 1000 1000 1000 3 3 4 4
7 1000 1000 1000 4 8 1000 3 1000 1000 4 1000
8 1000 1000 1000 6 1000 10 3 1000 1000 1000 7
9 1000 1000 1000 1000 1000 1000 4 4 1000 1000 4
10 1000 1000 1000 1000 1000 1000 4 1000 7 4 1000
The shortest distance is:20
The path is:
step 1 is a
and its label is0
step 2 is c
and its label is3
step 3 is f
and its label is4
step 4 is d
and its label is9
step 5 is h
and its label is13
step 6 is g
and its label is16
step 7 is k
and its label is20
Press any key to continue