29 lines
808 B
Dart
29 lines
808 B
Dart
|
List<int?> dijkstra(int from) {
|
||
|
|
List<int?> d = List<int?>.filled(_amount, intMax);
|
||
|
|
List<int> p = List<int>.filled(_amount, -1);
|
||
|
|
|
||
|
|
d[from - 1] = 0;
|
||
|
|
List<bool> u = List<bool>.filled(_amount, false);
|
||
|
|
for (int i = 0; i < _amount; ++i) {
|
||
|
|
int v = -1;
|
||
|
|
for (int j = 0; j < _amount; ++j) {
|
||
|
|
if (!u[j] && (v == -1 || d[j]! < d[v]!)) {
|
||
|
|
v = j;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (d[v] == intMax) break;
|
||
|
|
u[v] = true;
|
||
|
|
for (int to in _dots[v].getL().keys) {
|
||
|
|
int len = _dots[v].getL()[to]!;
|
||
|
|
if (!_useLength && len == 0) len = 1;
|
||
|
|
if (d[v]! + len < d[to - 1]!) {
|
||
|
|
d[to - 1] = d[v]! + len;
|
||
|
|
p[to - 1] = v;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for (int i = 0; i < d.length; i++) {
|
||
|
|
if (d[i] == intMax) d[i] = null;
|
||
|
|
}
|
||
|
|
return d;
|
||
|
|
}
|