Dijkstra's Search Algorithm
This program uses Dijkstra's search algorithm to find the shortest path between two cities.
All you have to do is define the road map, specify origin and destination cities, and the program will figure out
the rest.
Quirks & Factoids
- Multigraphs (loops and parallel edges) are allowed
- Directed graphs are not supported
- The largest allowable graph is the complete graph K25
- All city names are randomly generated at run time
In order to find a shortest path from
one city to another, the program needs a map to analyze. Define the map by specifying
cities below. Once you have the desired number of cities, choose an origin and a
destination. Then, proceed to the next step to place roads between these cities.
Now that you know you will be traveling from Origin to
Destination, it's time to define the roads between the cities.
If you do not define a road between two cities, there will be no direct path between the two cities
and the program will look for a path between the two by using intermediate cities. You may also
assign a distance to each road, so the program can assess the shortest path in the event that there
are multiple paths.
Processing...
