Data Structures & Algorithms in Dart (5/5)

26 min readSep 15, 2022

Graphs (Breadth-First Search — Depth-First Search — Dijkstra’s Algorithm)

Graphs are an instrumental data structure that can model a wide range of things: webpages on internet, the migration patterns of birds, even protons in the nucleus of an atom. This section gets you thinking deeply (and broadly) about using graphs and graph algorithms to solve real-world problems.

What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs.

A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges.

Circles in the graph below represent the vertices, and the edges are the lines that connect them.

Types of Graphs

Graphs come in a few different flavors. The following sections will describe their characteristics.

Weighted Graphs

In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.

Take the airline industry as an example. Here’s a network with varying flight paths:

In this example, the vertices represent cities, while the edges represent a route from ine city to another. The weight associated with each edge represents the airfare between the two cities. Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there!

Directed Graphs

As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse because an edge may only permit traversal in one direction. The diagram below represents a directed graph.

You can tell a lot from this diagram:

There’s a flight from Hong Kong to Tokyo.
There’s no direct flight from San Francisco to Tokyo.
You can buy a roundtrip ticket between Singapore and Tokyo.
There is no way to get from Tokyo to San Francisco.

Undirected Graphs

You can think of an undirected graph as a directed graph where all edges are bi-directional.

In an undirected graph:

Two connected vertices have edges going back and forth.
The weight of an edge applies to both directions.

Common Operations

There are a number of common operations that any graph needs to implement. Before you get to those, though, you need the basic building blocks, that is, the vertices and edges.

Defining a Vertex

The image below shows a collection of vertices. They’re not yet a graph:

To represent those vertices, add the following class inside graph.dart:

class Vertex<T> {
  const Vertex({
    required this.index,
    required this.data,
  });

  final int index;
  final T data;

  @override
  String toString() => data.toString();
}

Here, you’ve defined a generic Vertex class. A vertex has a unique index within its graph and holds a piece of data.

Defining Edge

To connect two vertices, there must be an edge between them. These are the lines in the image below:

Add an Edge class to graph.dart:

class Edge<T> {
  const Edge(
    this.source,
    this.destination, [
    this.weight,
  ]);

  final Vertex<T> source;
  final Vertex<T> destination;
  final double? weight;
}

Edge connects two vertices and has an optional weight. Not too complicated, is it?

Defining a Graph Interface

Now it’s time to define the common operations that the various flavors of graphs all share.

Start by creating an EdgeType enum and adding it to graph.dart:

enum EdgeType { directed, undirected }

This will Allow you to specify whether the particular graph you’re constructing has directed or undirected edges.

Now add the following Graph interface below EdgeType:

abstract class Graph<E> {
  Iterable<Vertex<E>> get vertices;

  Vertex<E> creatVertex(E data);

  void addEdge(
    Vertex<E> source,
    Vertex<E> destination, {
    EdgeType edgeType,
    double? weight,
  });

  List<Edge<E>> edges(Vertex<E> source);

  double? weight(
    Vertex<E> source,
    Vertex<E> destination,
  );
}

This interface describes the common operations for a graph:

vertices: Returns all of the vertices in the graph.
createVertex: Creates a vertex and adds it to the graph.
addEdge: Connects two vertices in the graph with either a directed or undirected edge. The weight is optional.
edges: Returns a list of outgoing edges from a specific vertex.
weight: Returns the weight of the edge between two vertices.

In the following sections, you’ll implement this interface in two ways, first using what’s called an adjacency list, and second an adjacency matrix. Keep reading to find out what these terms mean.

Adjacency List

The first graph implementation that you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Take the flight network you saw earlier as an example:

You can describe the relationship between the cities in this graph by listing out the adjacent cities for each location:

Implementation

An adjacency list is a graph, so you need to implement the Graph interface that you created earlier. Add the following code to graph.dart:

class AdjacencyList<E> implements Graph<E> {
  
  final Map<Vertex<E>, List<Edge<E>>> _connections = {};
  var _nextIndex = 0;

  @override
  Iterable<Vertex<E>> get vertices => _connections.keys;

  // more to come
}

Creating a Vertex

Add the missing createVertex method to AdjacencyList:

@override
Vertex<E> createVertex(E data) {
  // 1
  final vertex = Vertex(
    index: _nextIndex,
    data: data,
  );
  _nextIndex++;
  // 2
  _connections[vertex] = [];
  return vertex;
}

Here’s what’s happening:

You first create a new vertex with a unique index.
Then you add the vertex as a key in the _connections map. You haven’t connected it to any other vertices in graph yet, so the list of outgoing edges is empty.

Adding an Edge

To connect two vertices, you need to add an edge. Recall that there are directed and undirected edges:

Every edge in an undirected graph can be traversed in both directions. So if it’s an undirected graph, you need to add two edges, one from the source to the destination and another from the destination to the source.

@override
void addEdge(
  Vertex<E> source,
  Vertex<E> destination, {
  EdgeType edgeType = EdgeType.undirected,
  double? weight,
}) {
  // 1
  _connections[source]?.add(
    Edge(source, destination, weight),
  );
  // 2
  if (edgeType == EdgeType.undirected) {
    _connections[destination]?.add(
      Edge(destination, source, weight),
    );
  }
}

Retrieving the Outgoing Edges From a Vertex

Continue your work on implementation Graph by adding the edges method to AdjacencyList:

@override
List<Edge<E>> edges(Vertex<E> source) {
  return _connections[source] ?? [];
}

This gets the stored outgoing edges for the provides vertex. If source is unknown, the method returns an empty list.

Retrieving the Weight of an Edge

Recall that the weight is the cost of going from one vertex to another. For example, if the cost of a ticket between Singapore and Tokyo is $500, the weight of this bidirectional edge is 500:

Implement the missing weight method in AdjacencyList by adding the following code to the class:

@override
double? weight(
  Vertex<E> source,
  Vertex<E> destination,
) {
  final match = edges(source).where((edge) {
    return edge.destination == destination;
  });
  if (match.isEmpty) return null;
  return match.first.weight;
}

Here, you search for an edge from source to destination. If it exists, you return its weight.

Making Adjacency List Printable

The required methods for AdjacencyList are complete now, but it would also be nice to be able to print a description of your graph. To do that, override toString like so:

@override
String toString() {
  final result = StringBuffer();
  // 1
  _connections.forEach((vertex, edges) {
    // 2
    final destinations = edges. map((edge) {
      return edge.destination;
    }).join(', ');
    result.writln('$vertex --> $destinations');
  });
  return result.toString();
}

Here’s what’s going on in the code above:

You loop through every key-value pair in _connections.
For every vertex, find all of the destinations and join them into a single, comma-separated string.
Put each vertex and its destinations on a new line.

This will produce output with lines in the following format:

Singapore --> Hong Kong, Tokyo

You’ve finally completed your first graph! Try it out by building a network in the next section.

Building a Network

For this example, you’ll go back to the diagram you saw earlier and construct a network of flights with the prices as weights:

import 'package:starter/graph.dart';

void main() {
  final graph = AdjacencyList<String>();

  final singapore = graph.createVertex('Singapore');
  final tokyo = graph.createVertex('Tokyo');
  final hongKong = graph.createVertex('Hong Kong');
  final detroit = graph.createVertex('Detroit');
  final sanFrancisco = graph.createVertex('San Francisco');
  final washingtonDC = graph.createVertex('Washington DC');
  final austinTexas = graph.createVertex('Austin Texas');
  final seattle = graph.createVertex('Seattle');

  graph.addEdge(singapore, hongKong, weight: 300);
  graph.addEdge(singapore, tokyo, weight: 500);
  graph.addEdge(hongKong, tokyo, weight: 250);
  graph.addEdge(tokyo, detroit, weight: 450);
  graph.addEdge(tokyo, washingtonDC, weight: 300);
  graph.addEdge(hongKong, sanFrancisco, weight: 600);
  graph.addEdge(detroit, austinTexas, weight: 50);
  graph.addEdge(austinTexas, washingtonDC, weight: 292);
  graph.addEdge(sanFrancisco, washingtonDC, weight: 337);
  graph.addEdge(washingtonDC, seattle, weight: 277);
  graph.addEdge(sanFrancisco, seattle, weight: 218);
  graph.addEdge(austinTexas, sanFrancisco, weight: 297);

  print(graph);
}

Singapore --> Hong Kong, Tokyo
Tokyo --> Singapore, Hong Kong, Detroit, Washington DC
Hong Kong --> Singapore, Tokyo, San Francisco
Detroit --> Tokyo, Austin Texas
San Francisco --> Hong Kong, Washington DC, Seattle, Austin Texas
Washington DC --> Tokyo, Austin Texas, San Francisco, Seattle
Austin Texas --> Detroit, Washington DC, San Francisco
Seattle --> Washington DC, San Francisco

Finding the Weight

You can also obtain other helpful information such as the cost of a flight from Singapore to Tokyo. This is the weight of the edge between those two vertices.

Add the following code at the bottom of the main function:

final cost = graph.weight(singapore, tokyo)?.toInt();
print('It costs \$$cost to fly from Singapore to Tokyo.');
// It costs $500 to fly from Singapore to Tokyo.

Getting the Edges

Do you need to know what all the outgoing flights from San Francisco are? For that, you just call edges.

Add the code below at the bottom of main:

print('San Francisco Outgoing Flights: ');
print('-------------------------------- ');
for (final edge in graph.edges(sanFrancisco)) {
  print('${edge.source} to ${edge.destination}');
}

Running then will display the flights:

San Francisco Outgoing Flights:
--------------------------------
San Francisco to Hong Kong
San Francisco to Washington DC
San Francisco to Seattle
San Francisco to Austin Texas

Adjacency Matrix

An adjacency matrix uses a two-dimensional grid or table to implement the graph data structure. Each vertex has its own row and column in table. The cells where rows and columns intersect hold the edge weights. If any particular cell is empty, that is, if the weight is null, then that means there is no edge between the row vertex and the column vertex.

Below is an example of a directed graph that depicts a flight network. As before, the weight represents the cost of the airfare:

Implementation

Add a new class to graph.dart called AdjacencyMatrix:

class AdjacencyMatrix<E> implements Graph<E> {

  final List<Vertex<E>> _vertices = [];
  final List<List<double?>?> _weights = [];
  var _nextIndex = 0;

  @override
  Iterable<Vertex<E>> get vertices => _vertices;

  // more to come ...
}

Creating a Vertex

For every new vertex that you create, you have to add an additional column and row to the matrix.

The first step is to create a new column by adding an additional empty destination at the end of every row. The destination is empty because no other vertices have created an edge to the new vertex yet. In the following diagram you can see a new column 5 filled with empty weights:

@override
Vertex<E> createVertex(E data) {
  // 1
  final vertex = Vertex(
    index: _nextIndex,
    data: data,
  );
  _nextIndex++;
  _vertices.add(vertex);
  // 2
  for (var i = 0; i < _weights.length; i++) {
    _weights[i]?.add(null);
  }
  // 3
  final row = List<double?>.filled(
    _vertices.length,
    null,
    growable: true,
  );
  _weights.add(row);
  return vertex;
}

Adding Edges

Creating edges is as simple as adding weights to the matrix. There’s no Edge class to worry about.

Add the missing addEdge method to AdjacencyMatrix:

@override
void addEdge(
  Vertex<E> source,
  Vertex<E> destination, {
  EdgeType edgeType = EdgeType.undirected,
  double? weight,
}) {
  // 1
  _weights[source.index]?[destination.index] = weight;
  // 2
  if (edgeType == EdgeType.undirected) {
    _weights[destination.index]?[source.index] = weight;
  }
}

The logic here is similar to how you implemented addEdge in AdjacencyList previously:

Always add a directed edge.
If the edge type for the graph is undirected, then also add another edge going from the destination to the source.

Retrieving the Outgoing Edges From a Vertex

Add the edges method to AdjacencyMatrix:

@override
List<Edge<E>> edges(Vertex<E> source) {
  List<Edge<E>> edges = [];
  // 1
  for (var column = 0; column < _weights.length; column++) {
    final weight = _weights[source.index]?[column];
    // 2
    if (weight == null) continue;
    // 3
    final destination = _vertices[column];
    edges.add(Edge(source, destination, weight));
  }
  return edges;
}

Retrieving the Weight of an Edge

It’s easy to get the weight of an edge. Simply look up the value in the adjacency matrix.

Implement weight like so:

@override
double? weight(Vertex<E> source, Vertex<E> destination) {
  return _weights[source.index]?[destination.index];
}

Making Adjacency Matrix Printable

Finally, override toString so you can print out a readable description of your graph:

@override
String toString() {
  final output = StringBuffer();
  // 1
  for (final vertex in _vertices) {
    output.writeln('${vertex.index}: ${vertex.data}');
  }
  // 2
  for (int i = 0; i < _weights.length; i++) {
    for (int j = 0; j < _weights.length; j++) {
      final value = (_weights[i]?[j] ?? '.').toString();
      output.write(value.padRight(6));
    }
    output.writeln();
  }
  return output.toString();
}

Building a Network

You will reuse the same example from AdjacencyList:

Go back to the main method and replace this:

final graph = AdjacencyList<String>();

with the following:

final graph = AdjacencyMatrix<String>();

AdjacencyMatrix and AdjacencyList conform to the same Graph interface, so the rest of the code stays the same.

Run the code. The print(graph) portion of the code should give the following output:

0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
.     500.0 300.0 .     .     .     .     .
500.0 .     250.0 450.0 .     300.0 .     .
300.0 250.0 .     .     600.0 .     .     .
.     450.0 .     .     .     .     50.0  .
.     .     600.0 .     .     337.0 297.0 218.0
.     300.0 .     .     337.0 .     292.0 277.0
.     .     .     50.0  297.0 292.0 .     .
.     .     .     .     218.0 277.0 .     .

Graph Analysis

This chart compares the cost different graph operations for adjacency lists and adjacency matrices. V represents the number of vertices, and E represents the number of edges.

Breadth-First Search

Previously, you explored using graphs to capture relationships between objects. Remember that objects are just vertices, and edges represent the relationships between them.

Several algorithms exist to traverse or search through a graph’s vertices.Once such algorithm is the breath-first search (BFS) algorithm. The BFS algorithm visits the closest vertices from the starting vertex before moving on to further vertices.

BFS can be used to solve a wide variety of problems:

Generating a minimum-spanning tree.
Finding potential paths between vertices.
Finding the shortest path between two vertices.

How Breath-First Search Works

A breath-first search starts by selecting any vertex in a graph. The algorithm then explores all neighbors of this vertex before traversing the neighbors’ neighbors and so forth.

You’ll use the following undirected graph as an example to explore how BFS works:

import 'queue.dart';
import 'graph.dart';

extension BreathFirstSearch<E> on Graph<E> {
  List<Vertex<E>> breathFirstSearch(Vertex<E> source) {
    final queue = QueueStack<Vertex<E>>();
    Set<Vertex<E>> enqueued = {};
    List<Vertex<E>> visited = [];

    // 1
    queue.enqueue(source);
    enqueued.add(source);

    while (true) {
      // 2
      final vertex = queue.dequeue();
      if (vertex == null) break;
      // 3
      visited.add(vertex);
      // 4
      final neighborEdges = edges(vertex);
      for (final edge in neighborEdges) {
        // 5
        if (!enqueued.contains(edge.destination)) {
          queue.enqueue(edge.destination);
          enqueued.add(edge.destination);
        }
      }
    }

    return visited;
  }
}

Testing it Out

import 'package:starter/breath_first_search.dart';
import 'package:starter/graph.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 1);
  graph.addEdge(a, c, weight: 1);
  graph.addEdge(a, d, weight: 1);
  graph.addEdge(b, e, weight: 1);
  graph.addEdge(c, f, weight: 1);
  graph.addEdge(c, g, weight: 1);
  graph.addEdge(e, h, weight: 1);
  graph.addEdge(e, f, weight: 1);
  graph.addEdge(f, g, weight: 1);

  final vertices = graph.breathFirstSearch(a);
  vertices.forEach(print);
}

Run that and note the order that BFS explored the vertices in:

A
B
C
D
E
F
G
H

Performance

When traversing a graph using BFS, each vertex is enqueued once. This process has a time complexity of O(V). During this traversal, you also visit all the edges. The time it takes to visit all edges is O(E). Adding the two together means that the overall time complexity for breath-first search is O(V + E).

The space complexity of BFS is O(V) since you have to store the vertices in three separate structures: queue, enqueued and visited.

Depth-First Search

Previously, you looked at breath-first search (BFS), in which you had to explore every neighbor of a vertex before going to the next level. You’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.

There are a lot of applications for DFS:

Topological sorting.
Detecting a cycle.
pathfinding, such as in maze puzzles.
Finding connected components in a sparse graph.

To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you backtrack and explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.

How Depth-First Search Works

The following example will take you through a depth-first search. The graph below is the same as the one in the previous so you can see the difference between BFS and DFS.

import 'stack.dart';
import 'graph.dart';

extension DepthFirstSearch<E> on Graph<E> {
  List<Vertex<E>> depthFirstSearch(Vertex<E> source) {
    final stack = Stack<Vertex<E>>();
    final pushed = <Vertex<E>>{};
    final visited = <Vertex<E>>[];

    stack.push(source);
    pushed.add(source);
    visited.add(source);

    // more to come

    return visited;
  }
}

Traversing Vertices

Next, complete the method by replacing // more to come comment with the following:

// 1
outerLoop:
while (stack.isNotEmpty) {
  final vertex = stack.peek;
  // 2
  final neighbors = edges(vertex);
  // 3
  for (final edge in neighbors) {
    if (!pushed.contains(edge.destination)) {
      stack.push(edge.destination);
      pushed.add(edge.destination);
      visited.add(edge.destination);
      // 4
      continue outerLoop;
    }
  }
  // 5
  stack.pop();
}

Testing it Out

import 'package:starter/graph.dart';
import 'package:starter/depth_first_search.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 1);
  graph.addEdge(a, c, weight: 1);
  graph.addEdge(a, d, weight: 1);
  graph.addEdge(b, e, weight: 1);
  graph.addEdge(c, g, weight: 1);
  graph.addEdge(e, f, weight: 1);
  graph.addEdge(e, h, weight: 1);
  graph.addEdge(f, g, weight: 1);
  graph.addEdge(f, c, weight: 1);

  final vertices = graph.depthFirstSearch(a);
  vertices.forEach(print);
}

Run that and observe the order in which DFS visited the indices:

A
B
E
F
G
C
H
D

Performance

DFS will visit every single vertex at least once. This process has a time complexity of O(V).

When traversing a graph in DFS, you have to check all neighboring vertices to find one available to visit. The time complexity of this is O(E) because you have to visit every edge in the graph in the worst case.

Overall, The time complexity of depth-first search is O(V) since you have to store all the vertices in three separate data structures: stack, pushed and visited.

Cycles

A depth-first search is also useful for finding whether a graph contains cycles. A graph is said to have a cycle when a path of edges and vertices leads back to the same source.

For example, in the directed graph below, if you start at A, you can go to B, then to C, and then back to A again. Since it’s possible to arrive back at the starting vertex, this is a cyclic graph:

If you removed the C-to-A edge, this graph would become acyclic. That is, there would be no cycles. It would be impossible to start at any vertex and arrive back at the same vertex.

bool _hasCycle(Vertex<E> source, Set<Vertex<E>> pushed) {
  // 1
  pushed.add(source);
  // 2
  final neighbors = edges(source);
  for (final edge in neighbors) {
    // 3
    if (!pushed.contains(edge.destination)) {
      if (_hasCycle(edge.destination, pushed)) {
        return true;
      }
    // 4
    } else {
      return true;
    }
  }
  // 5
  pushed.remove(source);
  // 6
  return false;
}

Checking for Cycles

Next, you’ll write an algorithm to check whether a directed graph contains a cycle.

return to depth_first_search.dart and create another extension on Graph:

extension CycleGraph<E> on Graph<E> {

}

To complete the code, add the public hasCycle method to CyclicGraph:

bool hasCycle(Vertex<E> source) {
  Set<Vertex<E>> pushed = {};
  return _hasCycle(source, pushed);
}

You’re essentially performing a depth-first graph traversal by recursively diving down one path until you find a cycle and back-tracking by popping off the stack to find another path. The time complexity is O(V + E).

Testing it Out

final graph = AdjacencyList<String>();

final a = graph.createVertex('A');
final b = graph.createVertex('B');
final c = graph.createVertex('C');
final d = graph.createVertex('D');

graph.addEdge(a, b, edgeType: EdgeType.directed);
graph.addEdge(a, c, edgeType: EdgeType.directed);
graph.addEdge(c, a, edgeType: EdgeType.directed);
graph.addEdge(b, c, edgeType: EdgeType.directed);
graph.addEdge(c, d, edgeType: EdgeType.directed);

print(graph);
print(graph.hasCycle(a));

A --> B, C
B --> C
C --> A, D
D --> 

true

Dijkstra’s Algorithm

Have you ever used a maps app to find the shortest distance or fastest time from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two locations. The algorithm works with weighted graphs, both directed and undirected, to calculate the optimal routes from one vertex to all others in the graph.

Dijkstra’s algorithm is known as a greedy algorithm. That means it picks the most optimal path at every step along the way. It ignores solutions where some steps might have a higher intermediate cost but result in a lower overall cost for the entire path. Nevertheless, Dijkstra’s algorithm usually arrives at a pretty good solution very quickly.

Some applications of Dijkstra’s algorithm include:

Communicable disease transmission: Discovering where biological diseases are spreading the fastest.
Telephone networks: Routing calls to the highest-bandwidth paths available in the network.
Mapping: Finding the shortest and fastest paths for travelers.

How Dijkstra’s Algorithm Works

Imagine the directed graph below represents a road map. The vertices represent physical locations, and the edges represent one-way routes of a given cost between locations.

While edge weight can refer to the actual cost, it’s also commonly referred to as distance, which fits with the paradigm of finding the shortest route. However, if you like the word cost, you can think of route finding algorithms as looking for the cheapest route.

Initialization

In Dijkstra’s algorithm, you first choose a starting vertex since the algorithm needs a starting point to find a path to the rest of the nodes in the graph. Assume the starting vertex you pick is vertex A.

You’ll use a table to keep track of the shortest routes from A to the other vertices. In the beginning, you don’t know anything, so fill in the table with null values:

As you work through this example, you’ll use each cell of the table to save two pieces of information:

The shortest known distance from A to this vertex.
The previous vertex in the path.

First Pass

From vertex A, look at all of the outgoing edges. In this case, there are three:

A to B has a distance of 8.
A to F has a distance of 9.
A to G has a distance of 1.

Since you know the distance of traveling from A to these three vertices, write the values in the table:

You can see in the first cell that the distance from A to column B is 8. Below the 8 you also write A. This means that the previous vertex on the path to B is A. You’ll update both the distance and the previous vertex if you find a better path to B in the future. Columns F and G follow the same pattern. The other vertices are still null since there’s no known path to them from A yet.

Second Pass

In every round, Dijkstra’s algorithm always takes the shortest path. Of the distances 8, 9 and the shortest is 1. That means column G with the 1 is the direction that Dijkstra will go:

So the next step is to visit G:

Now, look for G’s outgoing edges. It only has one, which goes to C, and the distance is 3. That means the total distance of the A to C path is 1 + 3 = 4. So write 4 and G in the C column. Again, the reason you write G is that G is the previous vertex on this path before reaching C:

The filled-in vertices, both in the table and in the graph, are the ones you’ve visited. You already know the shortest route’s to these vertices, so you don’t need to check them anymore.

Third Pass

In the next pass, you look at the next-lowest distance. The distance to B is 8, the distance to C is 4, and the distance to F is 9. That means C is the winner:

So now you visit C:

Look at all of C’s outgoing edges and add up the total cost it would take to get there from A:

C to E has a total cost of 4 + 1 = 5.
C to B has a total cost of 4 + 3 = 7.

It’s actually cheaper to take this route to B than it was to go directly from A to B. Because of that update the B column with a new value of 7 by way of vertex C. Also fill in the E column since you know a route there now:

Fourth Pass

Of the unvisited vertices, which path has the lowest distance now? According to the table, E does, with a total distance of 5:

Visit E and check its outgoing vertices. You’ve already visited C so you can ignore that one. However, B and D are still unvisited:

These are the distances:

E to D has a total distance of 5 + 2 = 7.
E to B has a total distance of 5 + 1 = 6.

You didn’t know about D before, so you can fill in that column in the table. Also, when going to B, the path through E is even better than it was through C, so you can update the B column as well:

Fifth Pass

Next, you continue the search from B since it has the next-lowest distance:

Visit B and observe its edges:

Of B’s neighbors, the only one you haven’t visited yet is F. This has a total cost of 6 + 3 = 9. From the table, you can tell that the current path to F from A also costs 9. So, you can disregard this path since it isn’t any shorter:

Six Pass

Of the remaining unvisited vertices, D is closest to A with a distance of 7:

In this pass, continue the traversal from D:

However, D has no outgoing edges, so it’s a dead end. You can just move on.

Seventh Pass

F is up next. It’s the only unvisited vertex that you have any information about:

So visit F and observe its outgoing edges:

F has one outgoing edge to A, but you can disregard this edge since A is the starting vertex. You’ve already visited it.

Eighth Pass

You’ve covered every vertex except for H. H has one outgoing edge to G and one to F. However, there’s no path from A to H:

Becuase there’s no path, the column for H is null:

This step completes Dijkstra’s algorithm since all vertices that can be visited have been visited!

You can now check the table for the shortest paths and their distances. For example, the output tells you the distance you have to travel to get to D is 7. To find the path, you backtrack. Each column in the table records the previous vertex that the current vertex is connected to. For example, to find the path to D, you start D and backtrack. D points ti E, which points to C, which points to G, which ponts to A, the starting vertex. So the path is A-G-C-E-D:

Creating Distance-Vertex Pairs

In the example diagrams above, you saw that the tables contained a distance-vertex pai for every destination vertex. You’ll implement a class for this now to make it easier to pass these values around.

Create a new file in lib named dijkstra.dart and add the following code to it:

import 'graph.dart';

class Pair<T> extends Comparable<Pair<T>> {
  Pair(this.distance, [this.vertex]);

  double distance;
  Vertex<T>? vertex;

  @override 
  int compareTo(Pair<T> other) {
    if (distance == other.distance) return 0;
    if (distance > other.distance) return 1;
    return -1;
  }

  @override
  String toString() => '($distance, $vertex)';
}

Pair extends Comparable because Dijkstra’s algorithm hands the distance-vertex pairs to a priority queue. The internal heap requires comparable elements so that it can sort them. The comparison here is performed solely on the distance. Dijkstra will be on the lookout for the shortest distances.

Setting Up a Class for Dijkstra’s Algorithm

Add the following class to dijkstra.dart:

class Dijkstra<E> {
  Dijkstra(this.graph);

  final Graph<E> graph;
}

Dijkstra allows you to pass in any graph that implements the Graph interface.

Generating the shortest Paths

Now you’re ready to start building the actual algorithm.

Initializing Dijkstra’s Algorithm

First import the file with your priority queue data structure at the top of dijkstra.dart:

import 'priority_queue.dart';

Then add the following method to Dijkstra:

Map<Vertex<E>, Pair<E>? shortestPaths(Vertex<E> source) {
  // 1
  final queue = PriorityQueue<Pair<E>>(priority: Priority.min);
  final visited = <Vertex<E>>{};
  final paths = <Vertex<E>, Pair<E>?>{};
  // 2
  for (final vertex in graph.vertices) {
    paths[vertex] = null;
  }
  // 3
  queue.enqueue(Pair(0, source));
  paths[source] = Pair(0);
  visited.add(source);

  // more to come

  return path;
}

Visiting a New Vertex

Continue your implementation of shortestPath by replacing the // more to come comment with the following while loop. Each loop hanles visiting a new vertex:

// 1
while (!queue.isEmpty) {
  final current = queue.dequeue()!;
  // 2
  final saveDistance = paths[current.vertex]!.distance;
  if (current.distance > savedDistance) continue;
  // 3
  visited.add(current.vertex!);

  // more to come
}

Looping Over Outgoing Edges

You’re almost done. Now replace the // more to come comment inside the while loop with the following code. This for loop iterates over the outgoing edges of the current vertex:

for (final edge in graph.edges(current.vertex!)) {
  // final neighbor = edge.destination;
  // 1
  if (visited.contains(neighbor)) continue;
  // 2
  final weight = edge.weight ?? double.infinity;
  final totalDistance = current.distance + weight;
  // 3
  final knownDistance = paths[neighbor]?.distance ?? double.infinity;
  // 4
  if (totalDistance < knownDistance) {
    paths[neighbor] = Pair(totalDistance.current.vertex);
    queue.enqueue(Pair(totalDistance, neighbor));
  }
}

Trying it Out

import 'package:starter/dijkstra.dart';
import 'package:starter/graph.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 8, edgeType: EdgeType.directed);
  graph.addEdge(a, f, weight: 9, edgeType: EdgeType.directed;
  graph.addEdge(a, g, weight: 1, edgeType: EdgeType.directed;
  graph.addEdge(g, c, weight: 3, edgeType: EdgeType.directed;
  graph.addEdge(c, b, weight: 3, edgeType: EdgeType.directed;
  graph.addEdge(c, e, weight: 1, edgeType: EdgeType.directed;
  graph.addEdge(e, b, weight: 1, edgeType: EdgeType.directed;
  graph.addEdge(e, d, weight: 2, edgeType: EdgeType.directed;
  graph.addEdge(b, e, weight: 1, edgeType: EdgeType.directed;
  graph.addEdge(b, f, weight: 3, edgeType: EdgeType.directed;
  graph.addEdge(f, a, weight: 2, edgeType: EdgeType.directed;
  graph.addEdge(h, g, weight: 5, edgeType: EdgeType.directed;
  graph.addEdge(h, f, weight: 2, edgeType: EdgeType.directed;
}

final dijkstra = Dijkstra(graph);
final allPaths = dijkstra.shortestPaths(a);
print(allPaths);

{A: (0.0, null), B: (6.0, E), C: (4.0, G), D: (7.0, E), E: (5.0, 
C), F: (9.0, A), G: (1.0, A), H: null}

Finding a Specific Path

The shortestPaths method found the shortest route to all of the other reachable vertices. Often you just want the shortest path to single destination, through. You’ll add one more method to accomplish that.

List<Vertex<E>> shortestPath(
  Vertex<E> source,
  Vertex<E> destination, {
  Map<Vertex<E>, Pair<E>?>? paths, 
}) {
  // 1
  final allPaths = paths ?? shortestPaths(source);
  // 2
  if (!allPaths.containsKey(destination)) return [];
  var current = destination;
  final path = <Vertex<E>>[current];
  // 3
  while (current != source) {
    final previous = allPaths[current]?.vertex;
    if (previous == null) return [];
    path.add(previous);
    current = previous;
  }
  // 4
  return path.reversed.toList();
}

Trying it Out

final path = dijkstra.shortestPath(a, d);
print(path);

Run your code again and should see the ordered list of vertices showing the shortest path from A to D:

[A, G, C, E, D]

Just like in the example!

Performance

When performing Dijkstra’s algorithm, you need to visit every edge. That means the time complexity is at least O(E). After visiting an edge, you add the destination vertex to a priority queue if the distance for this edge is shorter. However, in a worst case scenario where every edge is shorter than the previous ones, you’d still have to enqueue a vertex for every edge. Since enqueuing and dequeuing with your heap-based priority queue has a logarithmic time complexity, this operation would be O(log E). Repeating that for every edge would thus be O(E log E).

What about when you visited all of the vertices at the begining of the algorithm to set the paths to null? That operation was O(V), so you could say the overall time complexity is O(V + E log E). However you, can assume that for a connected graph, V will be less than or approximately equal to E. That means you can replace O(V + E log E) with O(E + E log E). You can rearrange that as O(E x (1 + log E)). Then drop the 1 to again leave you with O(E log E). Remember that Big O notation is just a generalized way to talk about the complexity of an algorithm as the number of components increases. Constant values can be ignored.

Conclusion

Approaching a Difficult Problem

At times you may not even know what data structure or algorithm you should use to solve a particular problem. Here are a few ideas to help with that:

Draw a diagram to model the issue.
Talk through the problem with another developer.
Just get started by writing some code that “works”, even it’s horribly slow and inefficient.
Analyze what the time and space complexity are of your current implementation. How could they be improved?
Step through your current implementation line by line in a debugger. This often shows you useless tasks that your algorithm is performing.
Keep Reading and watching videos such my video on Youtube channel or anyone about data structures and algorithms that you’re unfamiliar with. The more you know, the more naturally a solution will pop into your head when you come up against a hard problem.

Learning Tips

Whenever you hear about a new data structure or algorithms that you’d like to learn, here are some steps you can take to maximize your learning experience:

Try to get an intuitive grasp of how the data is structured or how the algorithm works. Find illustrations or videos that describe it well. Draw yourself pictures or manipulate objects such as playing cards.
After you understand the data structure or algorithm on a conceptual level, try to implement it in code by yourself. Don’t look at other people’s implementations just yet. Imagine that you’re a computer scientist in the 1950s!
Finally check out the implementations in the other languages like C or Java or Python. Then convert them to Dart.

Data Structures & Algorithms in Dart (1/5)

Data Structures & Algorithms in Dart (2/5)

Data Structures & Algorithms in Dart (3/5)

Data Structures & Algorithms in Dart (4/5)