In graph theory, finding the shortest path on a graph refers to finding a path between two nodes such that the sum of the weights of its constituent links (edges) is minimum. For example, finding a shortest path between two cities corresponds to finding the quickest way to get from the first city to the destination city; in this case, if one represents the map as a graph, the nodes represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following generalizations:

**The single-source shortest path problem**: in which we have to find shortest paths from a source location (node) to all other nodes in the graph.**The single-destination shortest path problem**: in which we have to find shortest paths from all nodes in the graph to a single destination. This can be reduced to the single-source shortest path problem by reversing the edges in the graph.**The all-pairs shortest path problem**in which we have to find shortest paths between every pair of nodes in the graph.

Many algorithms are used to solve this problem, we have chosen to develop two of them:

*Dijkstra's algorithm*: solves the single-pair, single-source, and single-destination shortest path problems;*A* search algorithm*:solves the single-pair shortest path using heuristics to try to speed up the search.

This action allows the user to display the shortest path between
two nodes on the graph. All the links forming this path will be
highlighted. This action is available in both the Visualizer and the
Diagrammer. It is deactivated by default and is exclusive. The `ShortestPathAction`

class implements the interface `IAction`

and implements its
methods (activate, update, deactivate). This action takes as a parameter
an instance of `ShortestPathComputeData`

instance that has
the following properties:

*computeMethod*: indicates which algorithm will be used;*distanceFunction*: used to specify the distance formula between two nodes. By default the distance between two nodes is equal to the weight of the link between them

The following code shows how the user can use the `ShortestPathAction`

once it is registered.

function runPathFinding(param:int):void { var pathActionData:ShortestPathActionData = new ShortestPathActionData(); if(param==0) pathActionData.computeMethod = ActionConstants.DIJKSTRA_ALGORITHM; else pathActionData.computeMethod = ActionConstants.ASTAR_ALGORITHM; visualizer.activateAction(ShortestPathAction.ID,pathActionData); }