Application Center - Maplesoft

# Dijkstras Shortest Path Algorithm

You can switch back to the summary page by clicking here.

A Maple Package implementing
Dijkstra's Shortest Path Algorithm

Jay Pedersen
University of Nebraska at Omaha Student
E-mail:
jayped007@gmail.com

Code Version 3, Date 2007-05-31, Maple Version 11

Project: Implement Dijkstras Algorithm for determining shortest paths in a network.

 > restart; with(networks):

References

Dijkstra's Shortest Path algorithm is a well-known algorithm.  One place where it is

defined is in  'Network Flows' by Ravindra Ahuga, Thomas Magnanti, and James Orlin,

(c) 1993, ISBN 0-13-617549-X.

Storage of a network is done into a 'Forward Star' and 'Reverse Star' data structure.

These structures are also defined in 'Network Flows' in section 2.3 (Network

Representations).

Maple programming is described in "maple 9; Introductory Programming Guide"

from Maplesoft; ISBN 189451143-3.  Available from the maplesoft website.

Input Format (for Network definition)

The algorithm takes as input a string containing a network definition.

The assumption is made that nodes are numberd 1:N, where N is the number

of nodes.

A network definition is a list containing sublists with numeric sequences; which
define the network.

1. The first sublist contains the number of nodes in the network,
the number of arcs and the source node.

For example: [4, 7, 5] defines a network with 4 nodes and 7 arcs
and says that node 5 is the source node to find shortest paths from.

2. The remaining sublists define the arcs in the network.  Each

specifies the start node, end node and cost of traveling the arc.

For example: '2 5 15' defines an arc from 2 to 5 with cost 15.

Example network definion (4 nodes, 6 arcs, source node is 1):

net := [

[4, 6, 1],

[1, 2, 1],

[1, 3, 3],

[2, 3, 2],

[3, 2, 4],

[2, 4, 5],

[3, 4, 9]

];

Algorithm Code

Example Usage

Usage: The routine Dijkstras_Algorithm is invoked to determine the shortest

paths from the source node to destination nodes on the network that it is given.

Syntax: Dijkstras_Algorithm(network[, display_graph]);

Arguments:
Network - list defining the network (see "Input Format" section).
display_graph - true/false, if true => graphically display shortest paths
defaults to false if not specified (=> no graph if not specified)

 > net := [ [4, 6, 1], # 4 nodes, 6 arcs, source node: 1 [1, 2, 1], # arc 1 - from 1 to 2, cost=1 [1, 3, 3],[2, 3, 2],[3, 2, 4],[2, 4, 5],[3, 4, 9] ]: Dijkstras_Algorithm(net); # dont display graph

 shortest paths from source (from node 1):  To Node   Dist   Prev Node        2      1      1        3      3      1        4      6      2

 > # More complex network, show resulting graph net := [ [9,36,1], # 9 nodes, 36 arcs, source node 1 [1,2,5],  # arc from 1 to 2, cost 5 [1,3,9],[1,4,20],[1,5,4],[1,8,14],[1,9,15], [2,1,5],[2,3,6],[3,1,9],[3,2,6],[3,4,15], [3,5,10],[4,1,20],[4,3,15],[4,5,20],[4,6,7], [4,7,12],[5,1,4],[5,3,10],[5,4,20],[5,6,3], [5,7,5],[5,8,13],[5,9,6],[6,4,7],[6,5,3], [7,4,12],[7,5,5],[7,8,7],[8,1,14],[8,5,13], [8,7,7],[8,9,5],[9,1,15],[9,5,6],[9,8,5] ]: Dijkstras_Algorithm(net, true);

 shortest paths from source (from node 1):  To Node   Dist   Prev Node        2      5      1        3      9      1        4     14      6        5      4      1        6      7      5        7      9      5        8     14      1        9     10      5

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.