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
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.
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.
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 |
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
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)
| You must Sign In to use this message board. | |||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||
