|
Total distance = 20</pre>
The priority queue is implemented as a binary heap. The heap stores an index into its data array, so it can quickly update the weight of an item already in it.
=={{header|CafeOBJ}}==
=={{header|C}}==
<lang CafeOBJ>
<lang Cafe>
"
#include <stdio.h>
Save this file as DijkstraRosetta.cafe.
#include <stdlib.h>
To run the file type
#include <limits.h>
CafeOBJ> in DijkstraRosetta.cafe
at the CafeOBJ command prompt.
typedef struct {
CafeOBJ is primarily a first order specification language which can also be used as a functional programming language.
int vertex;
Being first order, we make no use higher order functions such as map.
int weight;
} edge_t;
typedef struct {
edge_t **edges;
int edges_len;
int edges_size;
int dist;
int prev;
int visited;
} vertex_t;
typedef struct {
Dijkstra's algorithm repeatedly chooses the nearest vertex and relaxes the edges leaving it, terminating when no more vertices are accessible from the origin.
vertex_t **vertices;
int vertices_len;
int vertices_size;
} graph_t;
typedef struct {
Input
int *data;
A directed positively weighted graph. The graph is represented as a list of 4tuples containing directed edges of the form (beginning, end, edgeDist,pathDist)
int *prio;
The tuple (start, start,0,0) means there is zero distance from start to start.
int *index;
int len;
int size;
} heap_t;
void add_vertex (graph_t *g, int i) {
Ouput
if (g->vertices_size < i + 1) {
1) a list of 4-tuples with each tuple represents a node N, its source, length of the conecting edge to N, and the shortest distance from the some starting node to N .
int size = g->vertices_size * 2 > i ? g->vertices_size * 2 : i + 4;
2) a list of nodes on the shortest path from a chosen start to some cosen end node.
g->vertices = realloc(g->vertices, size * sizeof (vertex_t *));
for (int j = g->vertices_size; j < size; j++)
g->vertices[j] = NULL;
g->vertices_size = size;
}
if (!g->vertices[i]) {
g->vertices[i] = calloc(1, sizeof (vertex_t));
g->vertices_len++;
}
}
void add_edge (graph_t *g, int a, int b, int w) {
Note needs a bit more work to exacly match the specified Rosetta Dijkstra task.
a = a - 'a';
"
b = b - 'a';
add_vertex(g, a);
add_vertex(g, b);
vertex_t *v = g->vertices[a];
if (v->edges_len >= v->edges_size) {
v->edges_size = v->edges_size ? v->edges_size * 2 : 4;
v->edges = realloc(v->edges, v->edges_size * sizeof (edge_t *));
}
edge_t *e = calloc(1, sizeof (edge_t));
e->vertex = b;
e->weight = w;
v->edges[v->edges_len++] = e;
}
heap_t *create_heap (int n) {
-- some system settings
heap_t *h = calloc(1, sizeof (heap_t));
-- Most important is memoization (memo) which stores the value of a function instead of recomputing it each time the function is called.
h->data = calloc(n + 1, sizeof (int));
full reset
h->prio = calloc(n + 1, sizeof (int));
set step off
h->index = calloc(n, sizeof (int));
set print fancy
return h;
set stats on
}
set verbose off
set quiet on
set memo on
void push_heap (heap_t *h, int v, int p) {
-- A module defining a simple parameterized list.
int i = h->index[v] == 0 ? ++h->len : h->index[v];
mod! LIST(T :: TRIV) principal-sort List {
int j = i / 2;
[Elt < List ]
op nil : -> List while (i > 1) {
if (h->prio[j] < p)
op (_:_) : List List -> List {memo assoc id: nil}
break;
op reverse_ : List -> List
h->data[i] = h->data[j];
op head_ : List -> Elt
h->prio[i] = h->prio[j];
var e : Elt
h->index[h->data[i]] = i;
var l : List
i = j;
eq reverse nil = nil .
eq reverse (e : l) = (reverse l) :j = j e/ .2;
eq head e : l = e .}
h->data[i] = v;
h->prio[i] = p;
h->index[v] = i;
}
int min (heap_t *h, int i, int j, int k) {
int m = i;
if (j <= h->len && h->prio[j] < h->prio[m])
m = j;
if (k <= h->len && h->prio[k] < h->prio[m])
m = k;
return m;
}
int pop_heap (heap_t *h) {
-- Main module
int v = h->data[1];
mod! DIJKSTRA {
int i = 1;
-- A four tuple used to store graph and shortest distance
while (1) {
-- start, end, edgeDist,pathDist
int j = min(h, h->len, 2 * i, 2 * i + 1);
pr(LIST(4TUPLE(INT,INT,INT,INT)))
if (j == h->len)
break;
-- A list of integers used to store final shortest path.
h->data[i] = h->data[j];
pr(LIST(INT) *{sort List -> PathList})
h->prio[i] = h->prio[j];
h->index[h->data[i]] = i;
[List < PathList]
op dijkstra___ : Int List Listi ->= Listj;
}
op exploreNeighbours___ : Int List List -> 4Tuple {memo}
h->data[i] = h->data[h->len];
ops inf finished : -> Int
h->prio[i] = h->prio[h->len];
op currDist__ : Int List -> Int
h->index[h->data[i]] = i;
op relax__ : List List -> List
h->len--;
op connectedTo__ : Int List -> Bool
return v;
op nextNode2Explore_ : List -> 4Tuple
}
op connectedList___ : List Int List -> List
op unvisitedList__ : List List -> List
op shortestPath__ : Int List -> PathList
op SP___ : 4Tuple 4Tuple List -> PathList
op shortestDist__ : Int List -> Int
op SD____ : Int Int List List -> Int
void dijkstra (graph_t *g, int a, int b) {
vars x y z n eD pD eD1 pD1 eD2 pD2 source currentVertex startVertex : Int
int i, j;
vars graph permanent xs : List
vars t t1a t2= a :- 4Tuple'a';
b = b - 'a';
for (i = 0; i < g->vertices_len; i++) {
vertex_t *v = g->vertices[i];
v->dist = INT_MAX;
v->prev = 0;
v->visited = 0;
}
vertex_t *v = g->vertices[a];
v->dist = 0;
heap_t *h = create_heap(g->vertices_len);
push_heap(h, a, v->dist);
while (h->len) {
i = pop_heap(h);
if (i == b)
break;
v = g->vertices[i];
v->visited = 1;
for (j = 0; j < v->edges_len; j++) {
edge_t *e = v->edges[j];
vertex_t *u = g->vertices[e->vertex];
if (!u->visited && v->dist + e->weight <= u->dist) {
u->prev = i;
u->dist = v->dist + e->weight;
push_heap(h, e->vertex, u->dist);
}
}
}
}
void print_path (graph_t *g, int i) {
eq inf =int 500n, .j;
vertex_t *v, *u;
eq finished = -1 .
i = i - 'a';
v = g->vertices[i];
if (v->dist == INT_MAX) {
printf("no path\n");
return;
}
for (n = 1, u = v; u->dist; u = g->vertices[u->prev], n++)
;
char *path = malloc(n);
path[n - 1] = 'a' + i;
for (j = 0, u = v; u->dist; u = g->vertices[u->prev], j++)
path[n - j - 2] = 'a' + u->prev;
printf("%d %.*s\n", v->dist, n, path);
}
int main () {
-- Main dijkstra function
graph_t *g = calloc(1, sizeof (graph_t));
eq dijkstra startVertex graph permanent =
add_edge(g, 'a', 'b', 7);
if (exploreNeighbours startVertex permanent graph) == << finished ; finished ; finished ; finished >> then permanent
add_edge(g, 'a', 'c', 9);
else (dijkstra startVertex graph ( ((exploreNeighbours startVertex permanent graph) : permanent))) fi .
add_edge(g, 'a', 'f', 14);
add_edge(g, 'b', 'c', 10);
eq exploreNeighbours startVertex permanent graph = (nextNode2Explore
add_edge(g, 'b', 'd', 15);
(relax (unvisitedList (connectedList graph startVertex permanent) permanent) permanent )) .
add_edge(g, 'c', 'd', 11);
add_edge(g, 'c', 'f', 2);
-- nextNode2Explore takes a list of records and returns a record with the minimum 4th element else finished
add_edge(g, 'd', 'e', 6);
eq nextNode2Explore nil = << finished ; finished ; finished ; finished >> .
add_edge(g, 'e', 'f', 9);
eq nextNode2Explore (t1 : nil) = t1 .
dijkstra(g, 'a', 'e');
eq nextNode2Explore (t2 : (t1 : xs)) = if (4* t1) < (4* t2) then t1 else nextNode2Explore (t2 : xs) fi .
print_path(g, 'e');
return 0;
-- relaxes all edges leaving y
}
eq relax nil permanent = nil .
eq relax (<< x ; y ; eD ; pD >> : xs) permanent = if (currDist x permanent) < pD then << y ; x ; eD ; ((currDist x permanent) + eD) >> : (relax xs permanent) else << y ; x ; eD ; pD >> : (relax xs permanent) fi .
-- Get the current best distance for a particulare vertex n.
eq currDist n nil = inf .
eq currDist n (t : permanent) = if ((1* t) == n) then (4* t ) else (currDist n permanent) fi .
eq connectedTo z nil = false .
eq connectedTo z ((<< x ; y ; eD ; pD >>) : xs) = if (x == z) then true else (connectedTo z xs) fi .
eq connectedList nil source permanent = nil .
eq connectedList (t : graph) source permanent = if (connectedTo source permanent) then
(t : (connectedList graph source permanent))
else (connectedList graph source permanent) fi .
eq unvisitedList nil permanent = nil .
eq unvisitedList (t : graph) permanent = if not(connectedTo (2* t) permanent) then (t : (unvisitedList graph permanent)) else (unvisitedList graph permanent) fi .
-- To get the shortest path we used the above dijkstra function.
-- From a given start to a given end we need to trace the path from the finish to the start and then reverse the output.
var pList : PathList
var currentTuple : 4Tuple
vars start end : Int
eq SP start end nil = nil .
eq SP start end (currentTuple : pList) = if (end == (1* currentTuple)) then ( end : (SP start (2* currentTuple) pList)) else (SP start end pList) fi .
-- The graph to be traversed
op DirectedRosetta : -> List
eq DirectedRosetta = ( << 1 ; 2 ; 7 ; inf >> :
<< 1 ; 3 ; 9 ; inf >> :
<< 1 ; 6 ; 14 ; inf >> :
<< 2 ; 3 ; 10 ; inf >> :
<< 2 ; 4 ; 15 ; inf >> :
<< 3 ; 4 ; 11 ; inf >> :
<< 3 ; 6 ; 2 ; inf >> :
<< 4 ; 5 ; 6 ; inf >> :
<< 5 ; 6 ; 9 ; inf >>) .
-- A set of possible strating points
ops oneStart twoStart threeStart fourStart fiveStart sixStart : -> List
eq oneStart = << 1 ; 1 ; 0 ; 0 >> .
eq twoStart = << 2 ; 2 ; 0 ; 0 >> .
eq threeStart = << 3 ; 3 ; 0 ; 0 >> .
eq fourStart = << 4 ; 4 ; 0 ; 0 >> .
eq fiveStart = << 5 ; 5 ; 0 ; 0 >> .
eq sixStart = << 6 ; 6 ; 0 ; 0 >> .
} -- End module
-- We must open the module in the CafeOBJ interpreter
open DIJKSTRA .
--> All shortest distances starting from a(1)
red dijkstra 1 DirectedRosetta oneStart .
-- Gives
-- ((((<< 5 ; 4 ; 6 ; 26 >>) : (<< 4 ; 3 ; 11 ; 20 >>)) : ((<< 6 ; 3 ; 2 ; 11 >>) : (<< 3 ; 1 ; 9 ; 9 >>))) : ((<< 2 ; 1 ; 7 ; 7 >>) : (<< 1 ; 1 ; 0 ; 0 >>))):List
--> Shortest path from a(1) to e(5)
red reverse (SP 1 5 (dijkstra 1 DirectedRosetta oneStart)) .
-- Gives
-- ((1 : 3) : (4 : 5)):PathList
--> Shortest path from a(1) to f(6)
red reverse (SP 1 6 (dijkstra 1 DirectedRosetta oneStart)) .
-- Gives
-- ((1 : 3) : 6):PathList
eof
</lang>
| 