13,344,508 members (48,221 online)
Add your own
alternative version

Stats

301.4K views
10K downloads
94 bookmarked
Posted 7 Aug 2007

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

License

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

About the Author

 Web Developer 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

 Pro

Comments and Discussions

 First Prev Next
 NEW And Easy code Member 842760320-Jan-12 17:49 Member 8427603 20-Jan-12 17:49
 Re: NEW And Easy code Amal Living Miracle6-Mar-13 2:11 Amal Living Miracle 6-Mar-13 2:11
 Re: NEW And Easy code Member 104422044-Dec-13 1:20 Member 10442204 4-Dec-13 1:20
 My vote of 1 amedi217-Jan-11 9:42 amedi21 7-Jan-11 9:42
 My vote of 1 chenghezhang2-Jan-11 16:42 chenghezhang 2-Jan-11 16:42
 tnx beykmohammadi7-Jun-10 21:12 beykmohammadi 7-Jun-10 21:12
 Bellman-Ford algorithm shahvishal10026-Nov-09 12:46 shahvishal100 26-Nov-09 12:46
 Re: Bellman-Ford algorithm yeyewa27-May-12 21:57 yeyewa 27-May-12 21:57
 Question Eng.Nanoos17-Oct-09 22:56 Eng.Nanoos 17-Oct-09 22:56
 My vote of 2 Paul8924-Apr-09 22:18 Paul89 24-Apr-09 22:18
 Small error but no biggie heavymetalman19-Nov-07 7:54 heavymetalman 19-Nov-07 7:54
 predecessor tree? real_iltfg4-Nov-07 8:17 real_iltfg 4-Nov-07 8:17
 Fear the naming convention QuaKx13-Aug-07 23:15 QuaKx 13-Aug-07 23:15
 Great Job madmemo9-Aug-07 2:00 madmemo 9-Aug-07 2:00
 maths filip_b7-Aug-07 13:23 filip_b 7-Aug-07 13:23
 Great Work Paddy Wack7-Aug-07 9:13 Paddy Wack 7-Aug-07 9:13
 Thanks. This applies directly to what I'm working on. Thanks !!!
 Last Visit: 31-Dec-99 19:00     Last Update: 16-Jan-18 17:13 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.180111.1 | Last Updated 14 Aug 2007
Article Copyright 2007 by dsdws
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid