Created
March 1, 2013 02:20
-
-
Save munificent/5062017 to your computer and use it in GitHub Desktop.
A slightly more idiomatic version of the Dart code from [this post](http://smthngsmwhr.wordpress.com/2013/02/25/javascript-and-friends-coffeescript-dart-and-typescript/).
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Graph { | |
num nodesNumber; | |
List<List<num>> edges; | |
Graph(this.nodesNumber, List<List<num>> edges) { | |
this.edges = new Iterable.generate(nodesNumber, | |
(_) => new List.fixedLength(nodesNumber)).toList(); | |
for (var e in edges) edge(e[0], e[1], e[2]); | |
} | |
void edge(num from, num to, num weight) { | |
edges[from - 1][to - 1] = weight; | |
} | |
Map _constructShortestPath(List<num> distances, List<num> previous, | |
List<num> unvisited, num to) { | |
var vertex = to; | |
var path = []; | |
while (vertex != null) { | |
path.add(vertex + 1); | |
vertex = previous[vertex]; | |
} | |
return { | |
'path': path, | |
'length': distances[to] | |
}; | |
} | |
num _getUnvisitedVertexWithShortestPath(List<num> distances, | |
List<num> previous, List<num> unvisited) { | |
return unvisited.min((a, b) => distances[a] - distances[b]); | |
} | |
void _updateDistancesForCurrent(List<num> distances, List<num> previous, | |
List<num> unvisited, num current) { | |
for (var i = 0; i < edges[current].length; i++) { | |
var currentEdge = edges[current][i]; | |
if (currentEdge != null && unvisited.contains(i)) { | |
if (distances[current] + currentEdge < distances[i]) { | |
distances[i] = distances[current] + currentEdge; | |
previous[i] = current; | |
} | |
} | |
} | |
} | |
// Dijkstra algorithm http://en.wikipedia.org/wiki/Dijkstra's_algorithm | |
Map getShortestPath(num from, num to) { | |
from = from - 1; | |
to = to - 1; | |
// Initialization | |
var unvisited = new Iterable.generate(nodesNumber, (i) => i).toList(); | |
var distances = new List.fixedLength(nodesNumber, fill: 1/0); | |
var previous = new List.fixedLength(nodesNumber); | |
distances[from] = 0; | |
var current = null; | |
while (true) { | |
if (!unvisited.contains(to)) { | |
return _constructShortestPath(distances, previous, unvisited, to); | |
} | |
current = _getUnvisitedVertexWithShortestPath(distances, previous, unvisited); | |
// No path exists | |
if (current == null || distances[current] == 1/0) { | |
return { | |
'path': [], | |
'length': 1/0 | |
}; | |
} | |
_updateDistancesForCurrent(distances, previous, unvisited, current); | |
unvisited.remove(current); | |
} | |
} | |
} | |
void main() { | |
var graph = new Graph(8, [ | |
[1, 2, 5], [1, 3, 1], [1, 4, 3], | |
[2, 3, 2], [2, 5, 2], | |
[3, 4, 1], [3, 5, 8], | |
[4, 6, 2], | |
[5, 7, 1], | |
[6, 5, 1] | |
]); | |
var shortestPath = graph.getShortestPath(1, 7); | |
print("path = ${shortestPath['path'].join(",")}"); | |
print("length = ${shortestPath['length']}"); | |
// No shortest path to the vertex '8' | |
print(graph.getShortestPath(1, 8)); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment