Add your own alternative version
Stats
288.7K views 18.4K downloads 99 bookmarked
Posted
23 Dec 2003

Comments and Discussions



Project is executable. I don't quite understand path relaxation. Perhaps a review of the textbook is required.





hi everybody
i need help in writing a code for Dijkstra’s algorithm to find
the leastcost paths in the network with node C as the source node.
Then, Construct a routing table based on the leastcost paths for node C.





program that tells the shortest path using dijkstra..thanks a lot..godbliz..take care...





i have code like this,,i use php languages..
this for map.php
<html>
<head>
<title>Find shortest route!</title>
<script> function clickMap(classID) {
if (document.form1.fromClass.value.length == 0)
{ document.form1.fromClass.value = classID; }
else { document.form1.toClass.value = classID; }
}
</script>
</head>
<body>
<img src="teiMap.jpg" usemap="#routes" border="0">
<map name="routes">
<area shape="rect" coords="225,50, 300, 100" href="java script:clickMap('1');" class="mymap"> <area shape="rect" coords="400,400,500,500" href="java script:clickMap('3');" class="mymap">
</area></area></map>
<form name="form1" action="coba.php" method="post">
From : <input type="text" name="fromClass" />
To : <input type="text" name="toClass" />
<input name="b1" type="submit" value="Enter!"> </input>
</form>
</img></body></html>
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,distancebetweenthem)
$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 '</br> ';
echo "<img src="\"maps/map_routes.jpg\"">";
//pagefooter();
?>
my question is, i have some problem if, i input 1 to 3 the result is from 123, but dijkstra algoritma i use is single graph,so algorima read same 13 with 31,,who know which one is wrong?? i want 13 not same 31 </img>





Hi, I am trying to implement a timer functionality to benchmark the algortihm, I want to see how long did the algorithm take to discover the shortest path. Can some one please please help me with that. Thanks





Hi,
I implemented another Dijkstra Algorithm by using Java.
However, I feel my program which i wrote is not good enough if there are two way that can go to a target node with the same cost.
I saw the cisco's design. if there are more than one way to go toa ip with same cost, The default action of cisco router is making it load balancing.
I met the difficulty in the issue, and downloaded the source but cannot find the ans too, could you mind giving me some tips about this issue? thx.





I just want to know if any of you have tried algorithms on shortest path.Articles on shortest path(Dijsktra's algorithm) in this forum did not
have a mechanism to create a node where edges crisscross each other.It is
required to create a topology of the road network to do so .Creation of topolgy needs finding of road intersections(beware of slope becoming infinity),which now become new nodes apart from existing nodes.The problem is complex/timeconsuming if the road network is denser.Is there a simple way to create topolgy for a road network and then find shortest path?





Hi all,
I want to implement Dijkstra's graph algo in C# , can anyone help me with code or useful links in this matter.
A code sample would do more help with complete implementation.
Desperately need help!
Ashish





What do you have to do to make the algorithm find the shortest path through ALL the points with the condition that it can only go to each point once? I guess this is like the classic travelling salesman problem.
Thanks in advance
Stephen





hey, i was wondering if anyone knows where to find code for a VB version of dijkstra's algorithm. any help would be greatly appreciated.
miro





Here you go http://en.giswiki.net/wiki/Dijkstra%27s_algorithm#Visual_Basic_6
Abhijit





crashed up in any Init function VC2003





Bravo Frate e mijto programul. Vroiam si eu sa pun un
algoritm al lui Dijkstra dar vad k lai pus tu.
Daca ai cumva un algoritm bun de sortare si poti sa ma juti as fi recunoscator.
Daca vrei putem tine legatura sa mai vb.
Bafta!
gabby





You will implement a version of Dijkstra's algorithm with slightly enhanced "bookkeeping" so that if there are several minimum distance paths from a source vertex to a destination vertex in a weighted directed graph, you will return the one that has the fewest number of edges.
Recall that Dijkstra's algorithm, as described in the text, allows us to solve the singlesource shortest weighted path problem: for a fixed source vertex s, we can calculate the shortest distance dv from s to v for every vertex v in the graph. The algorithm we have discussed also has "bookkeeping" to allow us to reconstruct one path whose distance is equal to the minimum distance dv.
Observe, however, that there can be several shortest distance paths from the source vertex s to the destination v. For example, consider the graph consisting of the following set of weighted directed edges, given by triples (from, to, cost):
NYC LosAngeles 400
NYC SanFrancisco 700
NYC SanDiego 600
LosAngeles SanDiego 100
SanDiego SanFrancisco 100
LosAngeles SanFrancisco 200
Imagine, for example, that the edge cost represents the price of a oneway flight from the departure city to the arrival city (for a fairly unusual airline). Then there are two paths from NYC (New York City) to San Francisco with minimum cost of 600:
NYC to LosAngeles to SanDiego to SanFrancisco
NYC to LosAngeles to SanFrancisco
Your program should return the second option, since that journey has only 2 legs rather than 3 legs.
Your assignment is to implement an efficient version of Dijkstra's algorithm with extra bookkeeping to allow the minimum distance path with fewest edges to be found. Only a few modifications to the pseudocode given in the text should be required. The main fact to keep in mind is the following (which is what makes the strategy in Dijkstra's algorithm work):
If s = v1 v2 ... vi ... vN = v is a minimum length path from s to v, then for every vertex vi along the path, it must also be true that v1 v2 ... vi is a minimum length path from s to vi.
Suggestion: first complete an efficient implementation of the Dijkstra's algorithm as given in the text, then think about what changes must be made to guarantee that you will also find the minimum cost path with fewest edges. Note that you should not keep track of all minimum length paths to do this.
Technical requirements:
· You must use a priority queue (heap) to allow you to efficiently find the unknown vertex with smallest distance for the main loop of Dijkstra's algorithm. You will need to extend the priority queue for allowing multiple entries for the same vertex and keeping track of whether vertices are known or unknown.
· Read the graph from a text file. You should do at least minimal error checking, such as rejecting negative edges. See the sample input file, flights.txt for an example.
· Allow the user to query source and destination vertices, and print out the minimum path with fewest edges using some kind of clear notation. Here is one example of acceptable output for the graph of cities given above:
· Enter start node:
· >NYC
· Enter destination node:
· >SanFrancisco
· NYC > LosAngeles > SanFrancisco
NewYorkCity Boston 100
Chicago NewYorkCity 200
NewYorkCity Hartford 200
Rochester NewYorkCity 200
NewYorkCity Rochester 200
NewYorkCity Seattle 400
Seattle LosAngelese 100
LosAngelese Seattle 150
Seattle Vancouver 100
Vancouver LosAngelese 250
Vancouver SanDiego 300
SanDiego Seattle 200
Chicago SanFrancisco 300
SanFrancisco LosAngelese 200
Chicago LosAngelese 400
Chicago Toronto 350
NewYorkCity Toronto 250
Toronto NewYorkCity 300
NewYorkCity LosAngelese 400
NewYorkCity SanFrancisco 700
NewYorkCity SanDiego 600
LosAngelese SanDiego 100
SanDiego SanFrancisco 100
LosAngelese SanFrancisco 200





Hello, maybe sumone listen.
Well, i'm "soso" with c++ and this is not very clear to me.
Sum Questions:
How to get notesdata in? Fortunately with Array. (with out clicking on form/non graphical aso..)
How to get calculated pathdata out?
Short: I need only the 3 Steps!
1.INPUT(notes,notesexitnotes) > 2.Algorithm > 3.OUTPUT(notes)
Would be very nice if sumone would/could help me!
Sorry for bad English...greets
Rino





You wrote: "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!"
You will indeed find this statement frequently in the literature, and I was told it when I did CompSci. However, the reason it's a counterinuitive result is that, in most cases of practical interest, it's not true!
For example, I can find the shortest path from my home in Strathfield, Australia to the post office in Strathfield, Australia, without pulling out a map of Guatemala!
If you can supply a heuristic estimate of the shortest path between two nodes, you can use the A* (A star) algorithm which can be billions of times faster and more spaceefficient than Dijkstra. You can always supply a heuristic in the important case of spatial coordinates (eg you can use the Euclidean distance between the two points).
So for transportation problems, robotics, and most games, Dijkstra is _not_ the best algorithm. A* deserves to be much better known.
I'm not intending to disparage your work in any way, as Dijkstra is the best algorithm in the most general case. This comment is purely for your information. Some day, I will get around to posting my AStar implementation to CodeProject.
The moral of the story is: Your intuition is probably better than you think!
Don.





Everyone can find the shortest path on a desert, but in the mountains we can see which algorithm is better. As CompSci master you should know the difference between the optimal algorithm and the heuristic.
Regardless of the difference let's compare algorithms:
Input data:  Dijkstra alg. needs the map (graph),  A* needs the map and the heuristic estimate So, A* needs more data and effort to use it.
Result:  Dijkstra alg. always provides optimal solution  A* sometimes provides optimal solution So, quality of solutions provided by Dijkstra algorithm are bettter.
Algorithm complexity  worst case  Dijkstra alg. O(n^3)  A* O(B(n)*n^3), where B is complexity of the computation of the heuristic estimate. 'Billions of times faster'  you must be joking. OK, I can imagine the graph where it is true, but it is far from reality.
Memory used: I don't know the memory requirements of the A*, but Dijkstra alg. uses array/list of n elements, so what can be so more spaceefficient. I've read somewhere that A* is infeasible for problems with huge number of nodes due to memory usage.
Finally I agree that for simple graphs (desert like) A* can be perfect.
The moral of the story is: Heuristic is never optimal





>As CompSci master you should know the difference >between the optimal algorithm and the heuristic.
> Heuristic is never optimal
True, but I think you've misunderstood the nature of A*. It is NOT a heuristic algorithm. You could in fact think of it as a specialised variant of Dijstra's algorithm to take advantage of additional information about the problem.
In Dijstra's algorithm, you visit neighbouring nodes in a random order. In A*, you use the heuristic to pick which nodes to visit first. Both do exactly the same work, but A* changes the order to maximise the probability of getting finished quickly.
>Input data:
> Dijkstra alg. needs the map (graph),
> A* needs the map and the heuristic estimate
>So, A* needs more data and effort to use it.
This is certainly true, if you want to get any advantage from it. But most workable heuristics are very simple.
> Dijkstra alg. always provides optimal solution
> A* sometimes provides optimal solution
If the heuristic you've provided is 'admissible' (heuristic <= actual distance), then the A* algorithm is guaranteed to provide an optimal solution. I have seen a formal proof of this. A* is only an approximate algorithm if your heuristic overestimates the actual distance.
For all geographical/spatial paths you can use Euclidean distance as the heuristic. A* is always better than Dijkstra for this important case.
>Algorithm complexity  worst case
> Dijkstra alg. O(n^3)
> A* O(B(n)*n^3), where B is complexity of the computation of the heuristic estimate.
Actually the heuristic needs to be computed only once per node. So A* is in O(B(n) + n^3) = O(n^3)
unless you have a fantastically stupid heuristic.
In the worst case A* and Dijkstra are equal. The data structures used are virtually identical, so the memory requirements are similar.
For A*, it's more relevant to consider it in terms of p, the length of the shortest path, rather than n, the number of nodes.
There is an equation I've seen but don't remember (on Gamasutra I think) that gives the complexity of A* as a function of p. It can be made independent of n.
>'Billions of times faster'  you must be joking. >OK, I can imagine the graph where it is true, but >it is far from reality.
Yes, I was just emphasizing the point that an
algorithm that is O(p^3) is much faster than an algorithm that is O(n^3)) where p << n, and is never worse because p is <= n by definition. Still, there are shortestpath algorithms for transport on the web where the user enters their location and destination. Such a system could conceivably include every road in the country, but most paths would be very short. It's not a completely contrived example.
The effectiveness of A* is as good as its heuristic. If you can provide a good one (and you frequently can), it is guaranteed to do much better than Dijkstra. This is true even for complex graphs.
But if you don't have a heuristic, you should use Dijkstra because it's simpler to implement.





A* (AStar) is a variation of the WaveFront algorithm. It requires a "map" on which to run an hence suffers from the discreteness of grids. The grid must be finer than the closest pair of points (Nyquist limit). Satisfying this rule can lead to pathological problems if there are other points in the domain that are far away. Running an A Star on 10,000x10,000 grid will beat up your hard drive pretty bad when it goes virtual.
Ironically, if Dijkdstra's algorithm is converted from a list into... a matrix representation is is much faster for a manageable set of nodes. It too will begin to suffer when N > 1000.





First: it is very good idea to present the algorithms in The Code Project.
Second:
I'm not quite sure.
I think the stop condition for the Dijkstra algorithm is:
The vertex that currently has the shortest path is the destination vertex.
It is very important especially for large graphs used in real problems, because algorithm goes very quickly to the destination vertex and stops, then it doesn't calculate the complete network.
Am I right?
Best regards





In the background the algorithm calculate the path to all nodes but I put in evidence (graphically) only the one I am interested in.
project manager
Solid understanding of Microsoft technologies: Windows ActiveX, COM / DCOM and ATL, SDK, STL, WTL, MFC





I reviewed my files, and I found that we used this improvement of the Dijkstra algorithm for searching shortest path in singlesourcesingledestination problem. Dijkstra algorithm is singlesource shortest path problem, as you mentioned in the article.
Other implementation problem. Algorithm complexity in your implementation is O(N^4) and Dijkstra algorithm is O(N^3). N  number of nodes. Would you mind considering correction of the function ExistEdge. In my opinion it is the error because complexity of ExistEdge should be O(1), and currently is O(N^2).
Best regards, MCS  Discrete Optimization





Yes, you are right! I admit that the code it isn't optimized. When I will get the time I will make those functions run faster.
Ciprian





Could you show us the optimized code if you have done something about it?





I am really glad that someone finally brough subject of algorithms into the Code Project. When I needed a starting point on graph algorithms 6 month ago, I could not find anything.
Thanks







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.

