Dijkstra's Shortest Path Algorithm

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Back in 2000, I posted a Graph Search unit that contained the data structure describing graphs (nodes and edges).  It has "depth first" and "breadth first" search procedures that look for ways to get from some starting node to some goal node.   I recently modified the structure to allow weights  to be associated with the edges which connect nodes.   A new procedure implements "Dijkstra's Shortest Path Search algorithm, a clever and relatively efficient way to search for shortest paths between nodes.   The algorithm finds the shortest paths from a specified start node to any other reachable node (or all reachable nodes) for graphs with positive weights (or costs, or distances) between nodes. 

Edsger Wybe Dijkstra, programmer, professor,  and mathematician,  invented and published his Shortest Path algorithm early in his career, around 1960 as best I can determine.  He died in 2002, but you can find many of his writings and learn more about his somewhat eccentric character by searching on his full name.  I would like to have known him.       

The immediate motivation was problem number 83 in the Euler Project programming challenges at ProjectEuler.net, a great site if you think you are a pretty good programmer.  There are other sections of the site with lots of good math problems that do not require programming skills.     In any event, Problem 83 asks for the shortest path from top left to bottom right of an 80x80 matrix of positive integers.  Omega Replica Watches Moves can be made up, down, left or right which is what makes the problem hard.  The demo program included here does not solve that problem, but could be adapted to do so, if you figure out how to represent the matrix as a graph. 

The demo randomly assigns weights to the same graph used in the 10 node graph in the original Graph Search demo program and calls the Dijkstra search procedure to  find the shortest path.  I have included a "verbose" feature that will let you see algorithm working step by step.   It works so well that I found several ways to improve the program when I  first ran "verbosely".   I think I'll add the same feature to Depth and Breadth first procedures one of these days. 

1. "Closest" unchecked is node 01 with weight to it = 0
2. Node 02 through node 01 has path weight 70
3. *** It is the smallest path so far from start to 02
2. Node 03 through node 01 has path weight 69
3. *** It is the smallest path so far from start to 03
4. All paths from 01 checked
1. "Closest" unchecked is node 03 with weight to it = 69
2. Node 06 through node 03 has path weight 94
3. *** It is the smallest path so far from start to 06
2. Node 07 through node 03 has path weight 70
3. *** It is the smallest path so far from start to 07
2. Node 10 through node 03 has path weight 122
3. *** It is the smallest path so far from start to 10
4. All paths from 03 checked
1. "Closest" unchecked is node 02 with weight to it = 70
2. Node 04 through node 02 has path weight 149
3. *** It is the smallest path so far from start to 04
2. Node 05 through node 02 has path weight 143
3. *** It is the smallest path so far from start to 05
4. All paths from 02 checked
1. "Closest" unchecked is node 07 with weight to it = 70
2. Node 10 through node 07 has path weight 121
3. *** It is the smallest path so far from start to 10
4. All paths from 07 checked
1. "Closest" unchecked is node 06 with weight to it = 94
4. All paths from 06 checked
1. "Closest" unchecked is node 10 with weight to it = 121
5. Destination node 10 found!

Shortest Path from 1 to 10:
Node: 01 Total distance so far: 0
Node: 03 Total distance so far: 69
Node: 07 Total distance so far: 70
Node: 10 Total distance so far: 121

Find shortest path from "1" to "10"

Dijkstra's Algorithm solution

Addendum October28, 2005:  The source for this program was repackaged today, moving UTGraphSearch, the unit that contains the graph list and search class, to a common DFF library file.  The purpose is to reduce the number of programs to be reposted when a widely used class or routine is fixed or enhanced.  The result is that a one time download of the DFF library file is required if you wish to recompile the program.  

Shortest 2 to 10 path
2-1-3-7-10

March 3, 2016:   The original demo calculated the shortest path from Node 1 to node 10 using random weights (distances) from node to node.  The search was one way but a programmer recently modified the program to search from node 2 to node 10  and reported a bug when the shortest path happened to be 2-1-3-7-10 which required traveling backwards through node 1.  Version 2.0 posted today incorporates two-way searching and allows users to specify both the start node and the goal node.  
 

Running/Exploring the Program 

bulletDownload source code
bulletDownload source code for current DFF library file (DFFLibV15 ).
bulletDownload executable 

 

bulletDownload Lazarus Source (not maintained)
bulletDownload current DFF Lazarus Library Source(DFFLazLib01) (not maintained)

 

 

 

 

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.