Skip to content

Instantly share code, notes, and snippets.

@munificent

munificent/gist:5062017

Created March 1, 2013 02:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save munificent/5062017 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save munificent/5062017 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. munificent created this gist Mar 1, 2013.
    98 changes: 98 additions & 0 deletions gistfile1.dart
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,98 @@
    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));
    }