Introduction

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:

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

Shortest Path Action

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:

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);
}