# Dijkstra's Shortest Path Algorithm

Where can I find a good explanation of Dijkstra’s Shortest Path Algorithm ?

This explains how it works:
http://algorithm.diy.myrice.com/resources/technical_artile/fibonacci_heap/fibonacci.htm

Dijkstra’s shortest-path algorithm finds the least expensive path through a weighted graph (also called a “network”).

Dijkstra’s algorithm sets the cost of each vertex (except the starting vertex) to infinity and puts all the vertices onto a heap. You then extract the cheapest vertex from the heap – call it M – and examine each vertex A adjacent to M. If the cost of M plus the cost of the edge joining M to A is cheaper than the current cost of A (that is, if there’s a cheap path to A through M), you create a link from A to M and decrease A’s key to represent the new cost. You continue extracting successive nodes until you reach T, the target vertex. The value of T is the cost of the shortest path. The links from T back to the starting vertex indicate the shortest path.

Here is pseudocode (varieties can be found all over the net):

Here is an actual implementation:
https://blenderartists.org/forum/viewtopic.php?t=60074

Is there a more simple explanation ?
Also I would like an example of it in pascal.

There’s a nice graphical explanation at: http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/

The explanation in the quote I posted really is the simplest I could find. It takes some time to grasp, but the algorithm itself actually is very simple.

Here are even more links (with images):
http://www.devmaster.net/articles/pathfinding/
http://www.cs.auckland.ac.nz/software/AlgAnim/dij-op.html

I don’t know what Pascal is exactly, but these archives should contain a Pascal implementation:
http://www.cs.sunysb.edu/~algorith/implement/syslo/distrib/

example 1 pascal
example 2 C
example 3 C EDIT: reread and it says Psudo Code. Found one thing a for loop that is more like basic then C. So it is not a real language.

would have been nice if one had been C++ like it claimed to be lol.

the main differance to a reader in pascal and c is that in pascal you will see

begin
code
end

in c you will see

{
code
}

the other differances are really major, invisible to a casual reader but emportaint to the progamer. Example: In Pascal variables are global. In c they are not.

Dammit.
How long a path? About 45 seconds from start to finish.

Here’s the info:
Open Source code:
Dijkstra by Freakintosh
Pascal
Dijkstra’s shortest path algorithm demonstrated.

http://www.digitalcalamity.org/developer/index.html

Yes but I couldn’t find what exactly I was looking for.

I did that at university and I think I kept my papers. I implemented it in C. Most other people in my class used java and it took 3 minutes to find the shortest path whereas mine took just 15 seconds or so. Pascal is a good choice too.

If I remember right, you just consider how costly each path is by weighing up certain attributes. I think Dijkstra’s algorithm minimizes past path cost and some estimation of future path cost together. I’ll have a look for it.

One for the intellectual joke thread: Did you know Dijktra has a daughter called Amber who can write with both hands?

Ah, osxrules, that was pretty awful!

I keep telling people to ignore the press on Java when deciding on when to use it. It is not a fast language no mater what those press releases say. It is an interpreted language (when all else is said and done) and therfore a couple orders of magnitude slower then compiled languges such C/C++ or Pascal. Thanks, osxrules for proving my point.

how does python speed compare to java speed

Not sure but compaired to any mature compiled language python or any other interpreted language is slow. Sorry but compiled languages create machine code for the target platform. This means nothing between the processor and the the program other then the platform itself.

All interpreted languages are stored as something other then machine code for the platform, then translated at run time by another piece of software which come up with the code to be used by the target platform. That extra step means it runs slower.

Java is not strickly speeking, considered an interpreted language. It is classed as machine code for a virtual machine. It is compiled from source code that is not neccessarily kept on the platform. An emulator for the virtual machine must be present in order to run the code… I tend to say that this is a mater of symantics and call a spade, a spade. To me what I typed above about Java is marketing to hide the fact it is just another interpreted language.

for Blender 2.53

several (OLD!) links do not work anymore
maybe ‘revive’ it ? If my version is like it should …