Population

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.

    B.The problem

    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?

C.The idea of program

    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".

    D.The major functions

    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()

    E.A little explanation

1. Download the input file http://www.staroceans.com/NickGraph.txt, put it in your "c:\" drive and "opmatrix" has a limit of 20, do you check if it exceeds it?
2. Please check the graph for the problem, make sure we are talking about the same graph. The "nameStr" is actually an array of char string in order to help you reading.

    ¡¡

    #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

    ¡¡

¡¡