Shortest Path Algorithm

Interactive Implementation OF Dijkstra's Shortest Path Algorithm

Definition of Dijkstra's Shortest Path

1. To find the shortest path between points, the weight or length of a path is calculated as the sum of the weights of the edges in the path.

2. A path is a shortest path is there is no path from x to y with lower weight.

3. Dijkstra's algorithm finds the shortest path from x to y in order of increasing distance from x. That is, it chooses the first minimum edge, stores this value and adds the next minimum value from the next edge it selects.

4. It starts out at one vertex and branches out by selecting certain edges that lead to new vertices.

5. It is similar to the minimum spanning tree algorithm, in that it is "greedy", always choosing the closest edge in hopes of an optimal solution.

Characteristics of a Shortest Path Algorithm:

Dijkstra's algorithm selects an arbitrary starting vertex and then branches out from the tree constructed so far. Each of the nodes it visits could be in the tree, in the fringes or unseen. The designators:

TREE - nodes in the tree constructed so far

FRINGE - not in the tree, but adjacent to some vertex in the tree

UNSEEN - all others

designate for each node in the graph whether the node is part of the shortest path tree, a part of the set of fringes adjacent to the nodes in the tree or a part of, as of yet, unseen set of graph nodes. A crucial step in the algorithm is the selection of the node from the fringe edge. The algorithm always takes the edge with least weight from the tree to the fringe node. This is an example of a greedy algorithm which are used in optimization problems. They make locally optimal choices in hope that this will provide a globally optimal solution. The Applet performs the following operations:

Add Node - adding a node to the graph

Remove a Node - deleting a node from the graph

Enter Weight - entering the weight of the edge

You may view the shortest path applet by clicking below:

Dijkstra's Shortest Path .

The Applet Operations

To begin, select Demo and view an example of the shortest path algorithm.
Then choose AddNode to enter a node into the graph.
Then choose Enter Weight to enter a weight for the edge.
You may then Draw Edge to connect two nodes.
Run will run Dijkstra's algorithm on the current graph.
Step will step through the graph node by node.
Reset will reset the graph to its original state.

Version JDK 1.2

Back to Menu .