Click here to Skip to main content
Click here to Skip to main content

Shortest Path Problem: Dijkstra's Algorithm

, 13 Aug 2007
Rate this:
Please Sign up or sign in to vote.
Using Dijkstra's Algorithm for finding shortest path problem

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 can be used for shortest path to destination in traffic network.

Using the Code

I will explain 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 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 below how the algorithm steps are 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

dsdws
Web Developer
Turkey Turkey
Mehmet Ali ECER is a computer engineer in Istanbul, Turkey. He is graduated from Istanbul Technical University. He is working as a software developer and an analyst. He uses C#, Aspx, Oracle(PLSQL), MsSql, MySql, PostgreSql, Java(jsp, jsf), C, C++, Vb.
 
www.mehmetaliecer.com
mehmetaliecer@gmail.com

Comments and Discussions

 
QuestionNEW And Easy code PinmemberMember 842760320-Jan-12 16:49 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication4
{
class Program
{
public int n = 0;
public int infinity = 999;
public int[,] arr;
private static int[] distArray;
private static int[] prevArray;
private static bool[] knownArray;
public int source;
 
///
/// ///////////////////////////////////////////////////////////
///
Below are functions used in the program
 

public void print(int dist)
{
{
if (prevArray[dist] != 0)
print(prevArray[dist]);
Console.Write("--->"+dist );}}
 
//////////////////////////////////////////////////////////////
public void read()
{
using (StreamReader reader = new StreamReader("D:\\test3.txt"))
{
string size;
string line = null;
string[] pars;
string last;
size = reader.ReadLine();
n = int.Parse(size);
arr = new int[n + 1, n + 1];
 
for (int i = 1; i <= n; i++)
{
line = reader.ReadLine();
for (int j = 1; j <= n; j++)
{
char[] delimiters = new char[] { ',', '\n' };
pars = line.Split(delimiters, StringSplitOptions.RemoveEmptyEntries);
arr[i, j] = int.Parse(pars[j - 1]);
}
}
last = reader.ReadLine();
source = int.Parse(last);
 

}
}
//////////////////////////////
public void initialize()
{
distArray = new int[n + 1];
prevArray = new int[n + 1];
knownArray = new bool[n + 1];
for (int i = 1; i <= n; i++)
{
knownArray[i] = false;
prevArray[i] = 0;
distArray[i] = 999;
distArray[source] = 0;
 
}
}
/////////////////////////////////
public void dijkstra()
{
int close1 = 0;
for (int i = 1; i <= n; i++)
{
int min = 9999;
for (int jj = 1; jj <= n; jj++)
{
if (!knownArray[jj] && distArray[jj] != 999)
if (distArray[jj] < min)
{
min = distArray[jj];
close1 = jj;
}
 
}
knownArray[close1] = true;
//////////////////////////////////
for (int a = 1; a <= n; a++)
{
if (arr[close1, a] != 999 && !knownArray[a])
{
if (distArray[a] > arr[close1, a] + distArray[close1])
{
distArray[a] = arr[close1, a] + distArray[close1];
prevArray[a] = close1;
}
}
}
}
}
////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
static void Main(string[] args)
{ int choice; char chr;
// char c;
string st;
int destin;
Program pg = new Program();
pg.read();
pg.initialize();
pg.dijkstra();
//////////////////////////////
do
{
Console.Clear();
Console.WriteLine("------------------------------");
Console.WriteLine("DIJKSTRA'S ALGORITHM FOR WEIGHTED SHORTEST PATH ");
Console.WriteLine("The Source Vertex is:"+pg.source);
Console.WriteLine("-------------------------------");
Console.WriteLine("1.View Shortest Path From Source To A Specific Vertex");
Console.WriteLine("2.View Shortest Path From Source To All Vertices");
Console.WriteLine("-------------------------------");
Console.Write("Please enter your choice\n");
 
choice = int.Parse(Console.ReadLine());
if (choice == 1)
{

Console.WriteLine("-------------------------------------------");
Console.WriteLine("Enter the destination vertex between 1-8:");
st = Console.ReadLine();
destin = int.Parse(st);
Console.WriteLine("The Shortest Path is: ");
Console.WriteLine("-------------------------------------------");
pg.print(destin);
}
/////////////////////////
if (choice == 2)
{

Console.WriteLine("-------------------------------------------");
Console.WriteLine("The Shortest Paths from Source to all vertices are:");

Console.WriteLine("-------------------------------------------");
for (int k = 1; k <= pg.n; k++)
{
pg.print(k);
Console.WriteLine();
}
}
Console.WriteLine();
Console.WriteLine("-------------------------------------------");
 
Console.Write("Do you want to continue: Enter Y or N\n");
chr = char.Parse(Console.ReadLine());
}
while (chr != 'n' && chr != 'N');
}
}
}
AnswerRe: NEW And Easy code PinmemberAmal Living Miracle6-Mar-13 1:11 
AnswerRe: NEW And Easy code PinmemberMember 104422044-Dec-13 0:20 
GeneralMy vote of 1 Pinmemberamedi217-Jan-11 8:42 
GeneralMy vote of 1 Pinmemberchenghezhang2-Jan-11 15:42 
Generaltnx Pinmemberbeykmohammadi7-Jun-10 20:12 
GeneralBellman-Ford algorithm Pinmembershahvishal10026-Nov-09 11:46 
GeneralRe: Bellman-Ford algorithm Pinmemberyeyewa27-May-12 20:57 
GeneralQuestion PinmemberEng.Nanoos17-Oct-09 21:56 
GeneralMy vote of 2 PinmemberPaul8924-Apr-09 21:18 
GeneralSmall error but no biggie Pinmemberheavymetalman19-Nov-07 6:54 
Questionpredecessor tree? Pinmemberreal_iltfg4-Nov-07 7:17 
GeneralFear the naming convention PinmemberQuaKx13-Aug-07 22:15 
GeneralGreat Job Pinmembermadmemo9-Aug-07 1:00 
Generalmaths Pinmemberfilip_b7-Aug-07 12:23 
GeneralGreat Work PinmemberPaddy Wack7-Aug-07 8:13 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 14 Aug 2007
Article Copyright 2007 by dsdws
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid