gistfile1.dart

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));
}