Article

# Dijkstra Algorithm

, 23 Dec 2003
 Rate this:
Shortest path (Dijkstra's Algorithm)

## Introduction

First of all I must say that I am glad that I can help CodeProject. I tried, and used code from this site and I never took the time to send some of my code. So, the part that it is missing from this site is the Algorithms part, which is important in the programming filed. Let's get into the problem now. The Djkstra algorithm it gives you a headache from the programming point of view. In one step it finds the shortest path to every node in the graph. I will go into the graph background (basics) and then I will present the implementation of this algorithm. This example has also some advanced programming techniques and technologies. I used an ActiveX control (that it is actually the Dijkstra solver) and a container application that use the functions. Also, the lists are made using STL

## How to use it

First compile the AnimAlg project and then run the Algorithms project. That's all!

## Background (graph theory)

Djikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem. The somewhat unexpected result that all the paths can be found as easily as one further demonstrates the value of reading the literature on algorithms!

This problem is related to the spanning tree one. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph,

G = (V,E) where V is a set of vertices and E is a set of edges. Dijkstra's algorithm keeps two sets of vertices: S the set of vertices whose shortest paths from the source have already been determined and V-S the remaining vertices. The other data structures needed are: d array of best estimates of shortest path to each vertex pi an array of predecessors for each vertex The basic mode of operation is: Initialize d and pi, Set S to empty, While there are still vertices in V-S, Sort the vertices in V-S according to the current best estimate of their distance from the source, Add u, the closest vertex in V-S, to S, Relax all the vertices still in V-S connected to u Relaxation The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v.

## Using the code

The container application only use the ActiveX Control. First, must include the control in a Dialog or a FormView, add a variable to it and then use the following code:
```void CAlgorithmsView::OnAddNode()
{
}

{
}

void CAlgorithmsView::OnShortestPath()
{
CShorthestPath dlg;
if(dlg.DoModal()==IDOK)
/* dialog to take 2 longs which means the path*/
{
m_Dijkstra.ShortestPath(dlg.m_node1, dlg.m_node2);
}
}
```

I will not go too much into the code, I tried to explain there using comments.

Basically, it respects the Graph Theory explained above and the Dijkstra's pseudocode.

## Graph Implementation

```class CGraph
{
public:
long GetNrNodes();
CGraph();
virtual ~CGraph();
VTYPE_NODE m_nodes; // array of nodes
VTYPE_EDGE m_edges; // array of edges
VTYPE_NODE_P d; // array of longs that contain
// the shortest path at every step
VTYPE_NODE_P pi; // array of longs that contain
// the predecessor of each node for the shortest path
};```
```class CNode
{
public:
CNode Copy();
double m_cost; // not used yet
long m_NodeNr; // node number
POINT m_p; // graphical point for that node
CNode();
virtual ~CNode();
};```
```class CEdge
{
public:
bool m_red; // used to draw the result
// (if an edge it is a part of the shortest path it is drawn in red)
double m_cost; // the cost of an edge (picked randomly between 0-9)
long m_secondNode; // the second node number
long m_firstNode; // the first node number
POINT m_secondPct; // graphical elements for drawing the edges
POINT m_firstPct;
CEdge();
virtual ~CEdge();
};
// the graph is oriented from the first node to the second node```

## The Dijkstra's Algorithm (Implementation)

```// The Dijkstra's algorithm
STDMETHODIMP CDijkstra::ShortestPath(long node1, long node2)
{
ReleaseGraph();
// init d and pi
InitializeSource(g, g.m_nodes[node1-1]);
// Set S empty
VTYPE_NODE S;
// Put nodes in Q
VTYPE_NODE Q;
VTYPE_NODE::iterator kl;
for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
{
CNode node = (*kl).Copy();
Q.push_back(node);
}
// Algorithm
while(Q.size())
{
CNode nod = ExtractMin(Q); // the minim value for
// the shortest path up to this step
S.push_back(nod);
// each vertex v which is a neighbour of u
VTYPE_NODE::iterator kl;
for(kl=g.m_nodes.begin(); kl<g.m_nodes.end(); kl++)
{
if(ExistEdge(nod, (*kl)))
{
bool gasit = false;
VTYPE_NODE::iterator kll;
for(kll=Q.begin(); kll<Q.end(); kll++)
{
if((*kll).m_NodeNr == (*kl).m_NodeNr)
gasit = true;
}
if(gasit)
Relax(nod, (*kl), GetEdgeVal(nod, (*kl)));
}
}
}
RefreshDone(node1, node2);
return S_OK;
}```

If you want to see how the algorithm works step by step see the link: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html

A list of licenses authors might use can be found here

## Share

Web Developer
Romania
Education Computer Engineering Faculty 1994-1999
University of Iasi ? Romania
Engineering degree: system and computers
Specialty: programmer analyst
Master: (Distributed Computing) 2001 - 2002
Final Project: Remote Access. Encrypted file transfer.
Accessing any computer?s desktop through Internet or LAN.
Technologies: COM, ATL, API, SDK, MFC

 First Prev Next
 Thank you LiaoVictor 22-Jan-14 15:10
 help hano2222 22-Mar-10 7:29
 help me plsss,,,, sumario 25-Aug-08 20:21
 i have code like this,,i use php languages..   this for map.php Find shortest route!
From : To :   and this for the dijkstra.php   class Dijkstra {   var \$visited = array(); var \$distance = array(); var \$previousNode = array(); var \$startnode =null; var \$map = array(); var \$infiniteDistance = 0; var \$numberOfNodes = 0; var \$bestPath = 0; var \$matrixWidth = 0;   function Dijkstra(&\$ourMap, \$infiniteDistance) { \$this -> infiniteDistance = \$infiniteDistance; \$this -> map = &\$ourMap; \$this -> numberOfNodes = count(\$ourMap); \$this -> bestPath = 0; }   function findShortestPath(\$start,\$to) { \$this -> startnode = \$start; for (\$i=0;\$i<\$this -> numberOfNodes;\$i++) { if (\$i == \$this -> startnode) { \$this -> visited[\$i] = true; \$this -> distance[\$i] = 0; } else { \$this -> visited[\$i] = false; \$this -> distance[\$i] = isset(\$this -> map[\$this -> startnode][\$i]) ? \$this -> map[\$this -> startnode][\$i] : \$this -> infiniteDistance; } \$this -> previousNode[\$i] = \$this -> startnode; } \$maxTries = \$this -> numberOfNodes; \$tries = 0; while (in_array(false,\$this -> visited,true) && \$tries <= \$maxTries) { \$this -> bestPath = \$this->findBestPath(\$this->distance,array_keys(\$this -> visited,false)); if(\$to !== null && \$this -> bestPath === \$to) { break; } \$this -> updateDistanceAndPrevious(\$this -> bestPath); \$this -> visited[\$this -> bestPath] = true; \$tries++; } }   function findBestPath(\$ourDistance, \$ourNodesLeft) { \$bestPath = \$this -> infiniteDistance; \$bestNode = 0; for (\$i = 0,\$m=count(\$ourNodesLeft); \$i < \$m; \$i++) { if(\$ourDistance[\$ourNodesLeft[\$i]] < \$bestPath) { \$bestPath = \$ourDistance[\$ourNodesLeft[\$i]]; \$bestNode = \$ourNodesLeft[\$i]; } } return \$bestNode; }   function updateDistanceAndPrevious(\$obp) { for (\$i=0;\$i<\$this -> numberOfNodes;\$i++) { if( (isset(\$this->map[\$obp][\$i])) && (!(\$this->map[\$obp][\$i] == \$this->infiniteDistance) || (\$this->map[\$obp][\$i] == 0 )) && ((\$this->distance[\$obp] + \$this->map[\$obp][\$i]) < \$this -> distance[\$i]) ) { \$this -> distance[\$i] = \$this -> distance[\$obp] + \$this -> map[\$obp][\$i]; \$this -> previousNode[\$i] = \$obp; } } }   function printMap(&\$map) { \$placeholder = ' %' . strlen(\$this -> infiniteDistance) .'d'; \$foo = ''; for(\$i=0,\$im=count(\$map);\$i<\$im;\$i++) { for (\$k=0,\$m=\$im;\$k<\$m;\$k++) { \$foo.= sprintf(\$placeholder, isset(\$map[\$i][\$k]) ? \$map[\$i][\$k] : \$this -> infiniteDistance); } \$foo.= "\n"; } return \$foo; }   function getResults(\$to) { \$ourShortestPath = array(); \$foo = ''; for (\$i = 0; \$i < \$this -> numberOfNodes; \$i++) { if(\$to !== null && \$to !== \$i) { continue; } \$ourShortestPath[\$i] = array(); \$endNode = null; \$currNode = \$i; \$ourShortestPath[\$i][] = \$i; while (\$endNode === null || \$endNode != \$this -> startnode) { \$ourShortestPath[\$i][] = \$this -> previousNode[\$currNode]; \$endNode = \$this -> previousNode[\$currNode]; \$currNode = \$this -> previousNode[\$currNode]; } \$ourShortestPath[\$i] = array_reverse(\$ourShortestPath[\$i]); if (\$to === null || \$to === \$i) { if(\$this -> distance[\$i] >= \$this -> infiniteDistance) { \$foo .= sprintf("no route from %d to %d. \n",\$this -> startnode,\$i); } else { \$foo .= sprintf(' from %d => to %d = %d (distance) Number of sports : %d: Follow the route (%s).'."\n" , \$this -> startnode,\$i,\$this -> distance[\$i], count(\$ourShortestPath[\$i]), implode('-',\$ourShortestPath[\$i])); } \$foo .= str_repeat('-',20) . "\n"; if (\$to === \$i) { break; } } } return \$foo; } } // end class // I is the infinite distance. define('I',1000); \$matrixWidth = 69;   // \$points is an array in the following format: (router1,router2,distance-between-them) \$points = array( array(0,1,5), array(1,2,2), array(1,8,2), array(1,9,2), array(1,10,2), array(2,3,1), array(2,7,3), array(3,4,1), array(3,5,1), array(3,7,1), array(4,5,1), array(4,6,1), array(4,7,2), array(5,6,1), array(5,13,3), array(6,7,3), array(6,14,1), array(7,8,1), array(7,10,3), array(7,11,1), array(7,12,2), array(7,14,2), array(8,9,3), array(8,10,2), array(8,11,3), array(9,10,2), array(9,15,1), array(9,17,2), array(10,11,1), array(10,17,1), array(10,18,1), array(11,12,1), array(11,18,2), array(12,13,1), array(12,18,1), array(12,19,1), array(12,20,1), array(14,22,2), array(15,16,1), array(16,17,2), array(16,21,1), array(17,18,1), array(17,21,1), array(17,25,2), array(18,19,1), array(18,21,1), array(19,20,1), array(19,21,1), array(19,22,2), array(19,23,1), array(21,23,3), array(21,24,2), array(21,25,1), array(22,23,1), array(23,24,2), array(24,25,3), array(24,26,2), array(25,26,2), array(25,27,1), array(26,27,3), array(26,28,1), array(27,28,2), array(27,29,1), array(28,29,3), array(28,30,2), array(29,30,3), array(30,31,2), array(31,32,1) );   \$ourMap = array();   // Read in the points and push them into the map   for (\$i=0,\$m=count(\$points); \$i<\$m; \$i++) { \$x = \$points[\$i][0]; \$y = \$points[\$i][1]; \$c = \$points[\$i][2]; \$ourMap[\$x][\$y] = \$c; \$ourMap[\$y][\$x] = \$c; }   // ensure that the distance from a node to itself is always zero // Purists may want to edit this bit out.   for (\$i=0; \$i < \$matrixWidth; \$i++) { for (\$k=0; \$k < \$matrixWidth; \$k++) { if (\$i == \$k) \$ourMap[\$i][\$k] = 0; } }   // initialize the algorithm class \$dijkstra = new Dijkstra(\$ourMap, I,\$matrixWidth);   // \$dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13... if (!isset(\$_POST['fromClass'])) { \$fromClass = \$_POST['fromSelected']; \$fromClass1 = \$_POST['fromSelectedClass']; } else { \$fromClass = \$_POST['fromClass']; \$fromClass1 = \$_POST['fromClass']; }   if (!isset(\$_POST['toClass'])) { \$toClass = \$_POST['toSelected']; \$toClass1 = \$_POST['toSelectedClass']; } else { \$toClass = \$_POST['toClass']; \$toClass1 = \$_POST['toClass']; }   \$dijkstra->findShortestPath(\$fromClass, \$toClass);   // Display the results   // pageheader("ii_icon"); echo '```';   echo "the map looks like:\n\n"; echo \$dijkstra -> printMap(\$ourMap); echo "\n\n The shortest route from place ".\$fromClass1." (".\$fromClass.") " ." to ".\$toClass1." (".\$toClass.") is the following : \n"; echo \$dijkstra -> getResults((int)\$toClass); echo '

```';   echo "";   //pagefooter(); ?>   my question is, i have some problem if, i input 1 to 3 the result is from 1-2-3, but dijkstra algoritma i use is single graph,so algorima read same 1-3 with 3-1,,who know which one is wrong?? i want 1-3 not same 3-1
 Implementing a Timer Functionality David James 16-Mar-08 5:16
 Question about Dijkstra Algorithm wongyum 11-Mar-08 16:11
 How to create Topology for road networks? dgpdgp 7-Aug-07 5:28
 Help for Dijkstra's graph algo in C# Asshish 4-Jul-07 18:43
 Question averys 24-May-07 3:22
 VB version of Dijkstra's Algorithm mergul 21-Apr-06 13:00
 Re: VB version of Dijkstra's Algorithm abhijitkolas 8-Apr-07 18:57
 crash kahnpost@freenet.de 30-Jul-05 10:38
 e bun euacela 15-Sep-04 1:46
 Got Some Problems! Help Please! RinoMerc 4-Jun-04 12:02
 Stop condition kozlowski 4-Jan-04 12:10
 Re: Stop condition lgcip 6-Jan-04 3:16
 Re: Stop condition kozlowski 6-Jan-04 13:49
 Re: Stop condition lgcip 6-Jan-04 20:28
 Re: Stop condition xumepoc 14-Sep-11 4:51
 Just a comment Anonymous 31-Dec-03 18:41
 help! Mr. Kevork 30-Dec-03 12:40
 Re: help! lgcip 2-Jan-04 23:41
 Application Usage Peter Ritchie 30-Dec-03 3:45
 Last Visit: 31-Dec-99 18:00     Last Update: 30-Aug-14 3:35 Refresh 1