Skip to content

Commit 0c55897

Browse files
make-github-pseudonymous-againmake-github-pseudonymous-again
committed
fix implementation of dijkstra
1 parent 6f97c6b commit 0c55897

File tree

8 files changed

+259
-200
lines changed

8 files changed

+259
-200
lines changed

‎js/dist/gn.js

Lines changed: 46 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1425,59 +1425,68 @@ exports.wblossom_n3_t = wblossom_n3_t;
14251425
/* js/src/001 undirected/offline/algo/sp/dijkstra.js */
14261426

14271427

1428-
var dijkstra_t = function(priority_queue_t){
1428+
/**
1429+
* @param {graph} g the graph
1430+
* @param {int} order number of vertices in the graph
1431+
*
1432+
* @param {vertex} source the source vertex from where to start the search
1433+
*
1434+
* @param {array} prev a list of predecessor
1435+
* initialized to id(source)
1436+
* @param {array} dist a list of distance for the source to each vertex
1437+
* initialized to Infinity
1438+
*
1439+
* @param {bool[]} used an array to keep track of visited vertices
1440+
* initialized to false
1441+
* @param {array} ref an array used to reference nodes from the priority queue
1442+
* initialized to null
1443+
* @param {PriorityQueue} left a priority queue used to order neighbours
1444+
* according to their distance to the source
1445+
*
1446+
*/
14291447

1430-
var dijkstra = function(g, order, s, prev, dist, used, busy){
1448+
var dijkstra = function ( g, order, source, prev, dist, used, ref, left ) {
14311449

1432-
var pred = function(a, b){ return dist[a[0]] < dist[b[0]]; };
1433-
var priority_queue = priority_queue_t(pred);
1434-
var left = new priority_queue();
1450+
var current;
14351451

1436-
used[s[0]] = true;
1437-
busy[s[0]] = true;
1452+
dist[source[0]] = 0;
1453+
ref[source[0]] = left.push( source );
14381454

1439-
g.eitr(s, function(_, u, w){
1440-
dist[u[0]] = w;
1441-
busy[u[0]] = true;
1442-
left.push(u);
1443-
});
1455+
while ( left.length ) {
14441456

1445-
while(left.length){
1457+
current = left.pop();
1458+
used[current[0]] = true;
14461459

1447-
var m = left.pop();
1448-
used[m[0]] = true;
1449-
1450-
g.eitr(m, function(_, u, w){
1451-
var y = u;
1452-
1453-
if(!used[y[0]]){
1460+
g.eitr( current, function ( _, other, weight ) {
14541461

1455-
var v = dist[m[0]] + w;
1462+
var distance, improved;
14561463

1457-
if(v < dist[y[0]]){
1458-
dist[y[0]] = v;
1459-
prev[y[0]] = m[0];
1460-
}
1461-
// /!\ FLAWED : if updated element y already in the queue
1462-
// the priority queue doesn't guarantee that the predicate will hold
1463-
// true --> should use a pq allowing updating operations.
1464-
if(!busy[y[0]]){
1465-
left.push(y);
1466-
busy[y[0]] = true;
1467-
}
1464+
if ( ! used[other[0]] ) {
1465+
1466+
distance = dist[current[0]] + weight;
14681467

1468+
improved = distance < dist[other[0]];
1469+
1470+
if ( improved ) {
1471+
dist[other[0]] = distance;
1472+
prev[other[0]] = current[0];
14691473
}
1470-
});
1471-
}
14721474

1473-
};
1475+
if ( ref[other[0]] === null ) {
1476+
ref[other[0]] = left.push( other );
1477+
}
1478+
else if ( improved ) {
1479+
left.decreasekey( ref[other[0]], other );
1480+
}
14741481

1475-
return dijkstra;
1482+
}
1483+
});
1484+
}
14761485

14771486
};
14781487

14791488

1480-
exports.dijkstra_t = dijkstra_t;
1489+
exports.dijkstra = dijkstra;
14811490

14821491
/* js/src/001 undirected/offline/algo/sp/floyd.js */
14831492

‎js/dist/gn.js.map

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎js/dist/gn.min.js

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎js/src/001 undirected/offline/algo/sp/dijkstra.js

Lines changed: 49 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,64 @@
11

22

3-
var dijkstra_t = function(priority_queue_t){
3+
/**
4+
* @param {graph} g the graph
5+
* @param {int} order number of vertices in the graph
6+
*
7+
* @param {vertex} source the source vertex from where to start the search
8+
*
9+
* @param {array} prev a list of predecessor
10+
* initialized to id(source)
11+
* @param {array} dist a list of distance for the source to each vertex
12+
* initialized to Infinity
13+
*
14+
* @param {bool[]} used an array to keep track of visited vertices
15+
* initialized to false
16+
* @param {array} ref an array used to reference nodes from the priority queue
17+
* initialized to null
18+
* @param {PriorityQueue} left a priority queue used to order neighbours
19+
* according to their distance to the source
20+
*
21+
*/
422

5-
var dijkstra = function(g, order, s, prev, dist, used, busy){
23+
var dijkstra = function ( g, order, source, prev, dist, used, ref, left ) {
624

7-
var pred = function(a, b){ return dist[a[0]] < dist[b[0]]; };
8-
var priority_queue = priority_queue_t(pred);
9-
var left = new priority_queue();
25+
var current;
1026

11-
used[s[0]] = true;
12-
busy[s[0]] = true;
27+
dist[source[0]] = 0;
28+
ref[source[0]] = left.push( source );
1329

14-
g.eitr(s, function(_, u, w){
15-
dist[u[0]] = w;
16-
busy[u[0]] = true;
17-
left.push(u);
18-
});
30+
while ( left.length ) {
31+
32+
current = left.pop();
33+
used[current[0]] = true;
34+
35+
g.eitr( current, function ( _, other, weight ) {
36+
37+
var distance, improved;
38+
39+
if ( ! used[other[0]] ) {
1940

20-
while(left.length){
21-
22-
var m = left.pop();
23-
used[m[0]] = true;
24-
25-
g.eitr(m, function(_, u, w){
26-
var y = u;
27-
28-
if(!used[y[0]]){
29-
30-
var v = dist[m[0]] + w;
31-
32-
if(v < dist[y[0]]){
33-
dist[y[0]] = v;
34-
prev[y[0]] = m[0];
35-
}
36-
// /!\ FLAWED : if updated element y already in the queue
37-
// the priority queue doesn't guarantee that the predicate will hold
38-
// true --> should use a pq allowing updating operations.
39-
if(!busy[y[0]]){
40-
left.push(y);
41-
busy[y[0]] = true;
42-
}
41+
distance = dist[current[0]] + weight;
4342

43+
improved = distance < dist[other[0]];
44+
45+
if ( improved ) {
46+
dist[other[0]] = distance;
47+
prev[other[0]] = current[0];
4448
}
45-
});
46-
}
4749

48-
};
50+
if ( ref[other[0]] === null ) {
51+
ref[other[0]] = left.push( other );
52+
}
53+
else if ( improved ) {
54+
left.decreasekey( ref[other[0]], other );
55+
}
4956

50-
return dijkstra;
57+
}
58+
});
59+
}
5160

5261
};
5362

5463

55-
exports.dijkstra_t = dijkstra_t;
64+
exports.dijkstra = dijkstra;

‎package.json

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
"dependencies": {},
77
"devDependencies": {
88
"aureooms-node-package": "^1.0.0",
9+
"aureooms-js-functools": "^0.0.5",
910
"aureooms-js-algo": "^0.4.1"
1011
},
1112
"scripts": {

‎test/js/src/undirected/offline/algo/sp/dijkstra.js

Lines changed: 39 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,57 @@
11

2-
var algo = require('aureooms-js-algo');
2+
var one, algo, functools;
33

4-
var check = function(label, n, s, edges, prev, dist){
4+
algo = require( "aureooms-js-algo" );
5+
functools = require( "aureooms-js-functools" );
56

6-
test('dijkstra #' + label, function(assert){
7+
one = function ( label, n, s, edges, prev, dist ) {
78

8-
var Graph = gn.dense_graph_t();
9-
10-
var priority_queue_t = function(pred){
11-
return algo.lazy_binomial_queue_t(pred, algo.opt_t);
12-
};
9+
test( "dijkstra #" + label, function () {
10+
11+
var Graph, PriorityQueue;
12+
var g, i, v, e, j, p, d, used, ref, left, predicate;
13+
14+
PriorityQueue = algo.__BinomialHeap__( algo.BinomialTreeWithParent );
1315

14-
var dijkstra = gn.dijkstra_t(priority_queue_t);
16+
Graph = gn.dense_graph_t();
1517

16-
var g = new Graph();
17-
var i = n;
18+
g = new Graph();
19+
i = n;
1820

19-
var v = new Array(i);
21+
v = new Array(i);
2022

21-
while(i--) v[n-i-1] = g.vadd();
23+
while ( i-- ) {
24+
v[n-i-1] = g.vadd();
25+
}
2226

23-
for(var j = 0; j < edges.length; ++j){
24-
var e = edges[j];
25-
g.eadd(v[e[0]], v[e[1]], e[2]);
27+
for ( j = 0 ; j < edges.length ; ++j ){
28+
e = edges[j];
29+
g.eadd( v[e[0]], v[e[1]], e[2] );
2630
}
2731

28-
var p = gn.sqmat(1, n, v[s][0]);
29-
var d = gn.sqmat(1, n, Infinity);
30-
var u = gn.sqmat(1, n, false);
31-
var b = gn.sqmat(1, n, false);
32+
p = gn.sqmat( 1, n, v[s][0] );
33+
d = gn.sqmat( 1, n, Infinity );
34+
used = gn.sqmat( 1, n, false );
35+
ref = gn.sqmat( 1, n, null );
36+
37+
predicate = function ( u, v ) {
38+
return d[u[0]] - d[v[0]];
39+
};
3240

33-
dijkstra(g, n, v[s], p, d, u, b);
41+
left = new PriorityQueue( predicate );
3442

35-
deepEqual(p, prev, 'prev');
36-
deepEqual(d, dist, 'dist');
43+
gn.dijkstra( g, n, v[s], p, d, used, ref, left );
44+
45+
deepEqual( p, prev, "prev" );
46+
deepEqual( d, dist, "dist" );
3747

3848
});
3949

4050
};
4151

4252

43-
var I = [
53+
[
54+
4455
[
4556
'1',
4657
10,
@@ -56,7 +67,7 @@ var I = [
5667
[4, 7, 6]
5768
],
5869
[1, 3, 9, 2, 3, 4, 1, 4, 9, 9],
59-
[10, 9, 6, 7, 11, 14, 14, 17, Infinity, Infinity]
70+
[10, 9, 6, 7, 11, 14, 14, 17, Infinity, 0]
6071
],
6172

6273
[
@@ -70,7 +81,7 @@ var I = [
7081
[0, 3, 7]
7182
],
7283
[0, 0, 3, 0],
73-
[Infinity, 6, 9, 7]
84+
[0, 6, 9, 7]
7485
],
7586

7687
[
@@ -89,14 +100,9 @@ var I = [
89100
[8, 3, 2]
90101
],
91102
[2, 2, 2, 2, 3, 3, 2, 8, 3],
92-
[Infinity, 7, Infinity, 2, 3, 4, Infinity, 6, 4]
103+
[Infinity, 7, 0, 2, 3, 4, Infinity, 6, 4]
93104
]
94105

95106

96107

97-
];
98-
99-
100-
for(var i = 0; i < I.length; ++i){
101-
check.apply(undefined, I[i]);
102-
}
108+
].forEach( functools.partial( functools.star, null, [one] ) );

0 commit comments

Comments
 (0)