Shortest Path Problem: Dijkstra's Algorithm

Title:       Shortest Path Problem: Dijkstra's Algorithm
Author:      Mehmet Ali ECER 
Email:       mehmetaliecer@gmail.com
Member ID:   1604764 
Language:    C# 2.0 
Platform:    .NET 2.0
Technology:  Console Application
Level:       Advanced
Description: Using Dijkstra's Algorithm for finding shortest path problem
Section      C# Algorithms
SubSection   Path Finding

• Download source - 24 Kb

Introduction

Dijkstra's algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. For example, if the vertices (nodes) of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities. Also, this algorithm using for shortest path to destination in traffic network.

Using the code

I will tell this algorithm over an example.

We are in A node and the problem is we must go other nodes with minimum cost. L[,] is our distances between pairs of nodes array.

int[,] L ={
                {-1,  5, -1, -1, -1,  3, -1, -1}, 
                { 5, -1,  2, -1, -1, -1,  3, -1}, 
                {-1,  2, -1,  6, -1, -1, -1, 10}, 
                {-1, -1,  6, -1,  3, -1, -1, -1},
                {-1, -1, -1,  3, -1,  8, -1,  5}, 
                { 3, -1, -1, -1,  8, -1,  7, -1}, 
                {-1,  3, -1, -1, -1,  7, -1,  2}, 
                {-1, -1, 10, -1,  5, -1,  2, -1} 
            };

D[] shows the cost array. We will write the shortest cost in D array. C[] shows the our nodes.

Pseudocode

function Dijkstra(L[1..n, 1..n]) : array [2..n]
    array D[2..n]
    set C 
    C <- {2, 3, 4, 5, 6, …, n}
    for i <- 2 to n
        D[i] <- L[1,i]
    repeat n - 2 times
        v <- C  // minimum D[v] extract to C
        v <- C - {v} 
        for each w in C do
            D[w] <- min(D[w], D[v] + L[v,w])
    return D

It is shown at below how the algorithm steps is worked:

D[]-> -1, 5,-1,-1,-1, 3,-1,-1 C[]-> -1, 1, 2, 3, 4, 5, 6, 7	D[]-> -1, 5,-1,-1,11, 3,10,-1 C[]-> -1, 1, 2, 3, 4,-1, 6, 7
D[]-> -1, 5, 7,-1,11, 3, 8,-1 C[]-> -1,-1, 2, 3, 4,-1, 6, 7	D[]-> -1, 5, 7,13,11, 3, 8,17 C[]-> -1,-1,-1, 3, 4,-1, 6, 7
D[]-> -1, 5, 7,13,11, 3, 8,10 C[]-> -1,-1,-1, 3, 4,-1,-1, 7	D[]-> -1, 5, 7,13,11, 3, 8,10 C[]-> -1,-1,-1, 3, 4,-1,-1,-1
D[]-> -1, 5, 7,13,11, 3, 8, 8 C[]-> -1,-1,-1,-1,-1,-1,-1,-1

Using the code

    class Dijkstra
    {        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

For bug reports and suggestions feel free to contact me at mehmetaliecer@gmail.com

Mehmet Ali ECER

References

http://en.wikipedia.org/wiki/Dijkstra's_algorithm
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
www.cs.itu.edu.tr/~oktug/BH/notlar/bolum6.pdf (Turkish)