Display program code

dijkstra.pl : Dijkstra's single-source shortest path algorithm
Single-source shortest path algorithm based on [Dijkstra 1959].
Given a weighted directed graph and a source node, shortest distances to all other nodes are computed. Nodes are numbered from 1, weights can be any numeric type.

How to use:
The graph is represented using edge/3 constraints:
edge(A,B,W): there is an edge between node A and node B, with weight W
The following operation is supported:
dijkstra(S): compute all distances from source node S
The resulting output is represented as:
distance(B,D): the distance from the source node to node B is D
Internal operations are:
scan(N,L): scan the neighbours of node N, which is at distance L from the source node, then get the next non-scanned node with the smallest label (distance)
relabel(N,L): if N is already scanned, do nothing; otherwise set the label of N to L

See also:
Uses Fibonnacci heaps (see fib_heap.pl).
Reference paper: Dijkstra's Algorithm with Fibonacci Heaps: An Executable Description in CHR. Jon Sneyers, Tom Schrijvers and Bart Demoen. WLP 2006.
See also shortestpaths.pl for an all-pairs shortest path algorithm.

Program: Change the code, then submit!

Console: Enter query or select example from below, then submit and wait for answer!

Select example query: 

WebCHR help - CHR Website - (c) Copyrights Martin Kaeser Uni Ulm 2007