GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/DijkstrasAlgorithm

GraphTheory

  

DijkstrasAlgorithm

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

DijkstrasAlgorithm(G, s, t)

DijkstrasAlgorithm(G, s, T)

DijkstrasAlgorithm(G, s)

Parameters

G

-

a graph with non-negative edge weights or no weights

s, t

-

vertices of the graph G

T

-

list of vertices of the graph G

Description

• 

If G is an unweighted graph, the edges are assumed all to have weight 1.

• 

If G is a weighted graph, DijkstrasAlgorithm('G','s','t') returns the cheapest weighted path from vertex s to vertex t in the graph G. If a path from s to t exists, the output is a list of the form [[s,...,t],w] where [s,...,t] is the path and w is the weight of that path.  If no such path exists the output is ,.

• 

In the second calling sequence where T is a list of vertices of G, this is short for [seq(DijkstrasAlgorithm(G,s,t), t=T)], save that the algorithm does not need to recompute cheapest paths.

• 

In the third calling sequence where no destination vertices are given, this is short for DijkstrasAlgorithm(G,s,Vertices(G)), i.e. the cheapest path from s to every vertex in G is output.

• 

To compute distances between all pairs of vertices simultaneously, use the AllPairsDistance command.  To ignore edge weights (and use a faster breadth-first search) use the ShortestPath command.

• 

If some edge weights are negative, the BellmanFordAlgorithm command can be used to compute the shortest path.

Examples

withGraphTheory:

C6Graph1,2,1,2,3,3,3,4,7,4,5,3,5,6,3,1,6,3

C6:=Graph 1: an undirected weighted graph with 6 vertices and 6 edge(s)

(1)

DijkstrasAlgorithmC6,1,4

1,6,5,4,9

(2)

DrawGraphC6

DijkstrasAlgorithmC6,1

1,0,1,2,1,1,2,3,4,1,6,5,4,9,1,6,5,6,1,6,3

(3)

GGraph1,2,2,1,3,2,2,3,2,3,1,2,4,5,2,5,6,2,6,4,2

G:=Graph 2: a directed weighted graph with 6 vertices and 7 arc(s)

(4)

DrawGraphG

DijkstrasAlgorithmG,1,3

1,3,2

(5)

DijkstrasAlgorithmG,4,6

4,5,6,4

(6)

DijkstrasAlgorithmG,1,6

,∞

(7)

See Also

AllPairsDistance

BellmanFordAlgorithm

ShortestPath

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam