Data Structures and Algorithms Rewind: Graph

Prologue

Data Structures and Algorithms Rewind is a series of notes / articles that will help me rewind all the basic / essential stuff of common data structures / algorithms. Most of the code snippets / contents will come from books below:

  • Algorithms 4th
  • Introduction to Algorithms 3rd
  • Foundations of Algorithms 5th
  • Algorithm Design Manual 2nd
  • Data Structures and Algorithms Analysis in Java 3rd

(I might tweak the code a little bit so the code / text won’t follow the original one identically. e.g. Using state-of-art libraries and proper namings)

Data Structures and Algorithms Rewind: Graph

  • Is there a way to connect one item to another by following the connections?
  • How many other items are connected to a given item?
  • What is the shortest chain of connections between this item and this other item?

To model such situations, we use abstract mathematical objects called graphs.

Undirected Graphs

Definitions and Terms

Definitions:

  • A graph is a set of vertices and a collection of edges that each connect a pair of vertices
  • A path in a graph is a sequence of vertices connected by edges. A simple path is one with no repeated vertices. A cycle is a path with at least one edge whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices). The length of a path or a cycle is its number of edges
  • A graph is connected if there is a path from every vertex to every other vertex in the graph. A graph that is not connected consists of a set of connected components, which are maximal connected subgraphs
  • A tree is an acyclic connected graph. A disjoint set of trees is called a forest. A spanning tree of a connected graph is a subgraph that contains all of that graph’s vertices and is a single tree. A spanning forest of a graph is the union of spanning trees of its connected components

Terms: Self-loop, Parallel edges, Adjacent, Incident, Subgraph, Density, Dense, Sparse, Bipartite

Data type

1
2
3
4
5
6
Graph(int V)
int V()
int E()
void addEdge(int v, int w)
Iterable<Integer> adj(int v)
String toString()

Representations

  • Adjacency matrix: Too much space cost
  • Array of edges: adj() would examine all the edges in the graph
  • Array of ajacency lists: Satisfies both use cases

Adjacency-list data structure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Graph {
private final int verticesCount;
private int edgesCount;
private Set<Integer>[] adjacencyLists;
public Graph(int verticesCount) {
this.verticesCount = verticesCount;
this.edgesCount = 0;
for (int vertice = 0; vertice < verticesCount; vertice++) {
adjacencyLists[vertice] = new HashSet<>();
}
}
public int getVerticesCount() {
return verticesCount;
}
public int getEdgesCount() {
return edgesCount;
}
public void addEdge(int v, int w) {
adjacencyLists[v].add(w);
adjacencyLists[w].add(v);
edgesCount++;
}
public Iterable<Integer> adjacencyList(int v) {
return adjacencyLists[v];
}
}

Graph Processing / Searching

1
2
3
Search(Graph G, int s)
boolean marked(int v)
int count()

The classic recursive method for searching in a connected graph mimics Tremaux maze explorations. To search a graph, invoke a recursive method that visits vertices. To visit a vertex:

  • Mark it as having been visited
  • Visit (recursively) all the vertices that are adjacent to it and that have not yet been marked
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class DepthFirstSearch {
private boolean[] marked;
private int count;
public DepthFirstSearch(Graph graph, int start) {
this.marked = new boolean[graph.getVerticesCount()];
doDepthFirstSearch(graph, start);
}
private void doDepthFirstSearch(Graph graph, int start) {
marked[start] = true;
count++;
for (int w : graph.adjacencyList(start)) {
if (!marked[w]) {
doDepthFirstSearch(graph, w);
}
}
}
public boolean marked(int w) {
return marked(w);
}
public int count() {
return count;
}
}

Proposition: DFS marks all the vertices connected to a given source in time proportional to the sum of their degrees.

We could use DFS to address:

  • Conenctivity: Given a graph, support queries of the form Are two given vertices connected? and How many connected components does the graph have?
  • Single-source paths: Given a graph and a source vertex s, support queries of the form Is there a path from s to a given target vertex v? If so, find such a path
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int source;
public DepthFirstPaths(Graph graph, int source) {
this.marked = new boolean[graph.getVerticesCount()];
this.edgeTo = new int[graph.getVerticesCount()];
this.source = source;
doDepthFirstSearch(graph, source);
}
private void doDepthFirstSearch(Graph graph, int v) {
marked[v] = true;
for (int w : graph.adjacencyList(v)) {
if (!marked[w]) {
edgeTo[w] = v;
doDepthFirstSearch(graph, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public List<Integer> pathTo(int v) {
if (!hasPathTo(v))
return null;
List<Integer> result = new ArrayList<>();
for (int x = v; x != source; x = edgeTo[x]) {
result.add(x);
}
result.add(source);
return result;
}
}

Proposition: DFS allows us to provide clients with a path from given source to any marked vertex in time proportional its length.

Single-source shortest paths: Given a graph and a source vertex s, support queries of the form Is there a path from s to a given target vertex v? If so, find a shortest such path (one with a minimal number of edges)

DFS is analogous to one person exploring a maze. BFS is analogous to a group of researchers exploring by fanning out in all directions, each unrolling his or her own ball of string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int source;
public BreadthFirstPaths(Graph graph, int source) {
this.marked = new boolean[graph.getVerticesCount()];
this.edgeTo = new int[graph.getVerticesCount()];
this.source = source;
doBreadthFirstSearch(graph, source);
}
private void doBreadthFirstSearch(Graph graph, int s) {
Queue<Integer> queue = new ArrayDeque<>();
marked[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : graph.adjacencyList(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.add(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public List<Integer> pathTo(int v) {
if (!hasPathTo(v))
return null;
List<Integer> result = new ArrayList<>();
for (int x = v; x != source; x = edgeTo[x]) {
result.add(x);
}
result.add(source);
return result;
}
}

Proposition: For any vertex v reachable from s, BFS computes a shortest path from s to v. BFS takes time proportional to V + E in the worst case.

Connected Components

1
2
3
4
ConectedComponent(Graph g)
boolean connected(int v, int w)
int count()
int id(int v)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class ConnectedComponent {
private boolean[] marked;
private int[] id;
private int count;
public ConnectedComponent(Graph graph) {
this.marked = new boolean[graph.getVerticesCount()];
this.id = new int[graph.getVerticesCount()];
for (int s = 0; s < graph.getVerticesCount(); s++) {
if (!marked[s]) {
doDepthFirstSearch(graph, s);
count++;
}
}
}
private void doDepthFirstSearch(Graph graph, int v) {
marked[v] = true;
id[v] = count;
for (int w : graph.adjacencyList(v)) {
if (!marked[w]) doDepthFirstSearch(graph, w);
}
}
public boolean connected(int v, int w) {
return id[v] == id[w];
}
public int id(int v) {
return id[v];
}
public int count() {
return count;
}
public List<List<Integer>> components() {
List<List<Integer>> result =
IntStream.range(0, count)
.mapToObj(i -> new ArrayList<Integer>())
.collect(Collectors.toList());
IntStream.range(0, id.length).forEach(i -> result.get(id[i]).add(i));
return result;
}
}

Proposition: DFS uses preprocessing time and space proportional to V + E to support constant-time connectivity queries in a graph.

Cycle Detection

Is a given graph acylic?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Cycle {
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph graph) {
this.marked = new boolean[graph.getVerticesCount()];
for (int s = 0; s < graph.getVerticesCount(); s++) {
if (!marked[s]) doDepthFirstSearch(graph, s, s);
}
}
private void doDepthFirstSearch(Graph graph, int v, int u) {
marked[v] = true;
for (int w : graph.adjacencyList(v)) {
if (!marked[w]) doDepthFirstSearch(graph, w, v);
else if (w != u) hasCycle = true;
}
}
public boolean hasCycle() {
return hasCycle;
}
}
Two-colorability

Can the vertices of a given graph be assigned one of two colors in such a way that no edge connect vertices of the same color? which is equivalent to: Is the graph bipartite?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class TwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColorable = true;
public TwoColor(Graph graph) {
this.marked = new boolean[graph.getVerticesCount()];
this.color = new boolean[graph.getVerticesCount()];
for (int s = 0; s < graph.getVerticesCount(); s++) {
if (!marked[s]) doDepthFirstSearch(graph, s);
}
}
private void doDepthFirstSearch(Graph graph, int v) {
marked[v] = true;
for (int w : graph.adjacencyList(v)) {
if (!marked[w]) {
color[w] = !color[v];
doDepthFirstSearch(graph, w);
} else if (color[w] == color[v]) isTwoColorable = false;
}
}
public boolean isBipartite() {
return isTwoColorable;
}
}

Directed Graphs

Glossary

A directed graph (or digraph) is a set of vertices and a collection of directed edges. Each directed edge connects an ordered pair of vertices.

A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence.

A directed cycle is a directed path with at least one edge whose first and last vertices are the same.

A simple path is a path with no repeated vertices.

A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices).

The length of a path or a cycle is its number of edges.

Digraph data type

1
2
3
4
5
6
7
Digraph(int V)
int V()
int E()
void addEdge(int v, int w)
Iterable<Integer> adj(int v)
Digraph reverse()
String toString()

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Digraph {
private final int verticesCount;
private int edgesCount;
private Set<Integer>[] adjacencyLists;
public Digraph(int verticesCount) {
this.verticesCount = verticesCount;
this.edgesCount = 0;
this.adjacencyLists = (Set<Integer>[]) new Set[verticesCount];
for (int v = 0; v < verticesCount; v++) {
adjacencyLists[v] = new TreeSet<>();
}
}
public int getVerticesCount() {
return verticesCount;
}
public int getEdgesCount() {
return edgesCount;
}
public Set<Integer> adjacentVertices(int v) {
return adjacencyLists[v];
}
public void addEdge(int v, int w) {
adjacencyLists[v].add(w);
edgesCount++;
}
public Digraph reverse() {
Digraph reversed = new Digraph(verticesCount);
for (int v = 0; v < verticesCount; v++) {
for (int w : adjacencyLists[v]) {
reversed.addEdge(w, v);
}
}
return reversed;
}
@Override
public String toString() {
return MoreObjects.toStringHelper(this)
.add("VerticesCount", verticesCount)
.add("EdgesCount", edgesCount)
.add("Edges",
IntStream.range(0, adjacencyLists.length)
.mapToObj(i -> i + ": " + adjacencyLists[i]).collect(Collectors.joining("\r\n")))
.toString();
}
}

Reachability in digraphs

Single-source reachability: Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v?

Multiple-source reachability: Given a digraph and a set of source vertices, support queries of the form Is there a directed path from some vertex in the set to a given target vertex v?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class DirectedDfs {
private boolean[] marked;
public DirectedDfs(Digraph graph, int source) {
marked = new boolean[graph.getVerticesCount()];
doDfs(graph, source);
}
public DirectedDfs(Digraph graph, Iterable<Integer> sources) {
marked = new boolean[graph.getVerticesCount()];
for (int s : sources) {
if (!marked[s]) {
doDfs(graph, s);
}
}
}
private void doDfs(Digraph graph, int v) {
marked[v] = true;
for (int w : graph.adjacentVertices(v)) {
if (!marked[w]) {
doDfs(graph, w);
}
}
}
public boolean marked(int v) {
return marked[v];
}
@Override
public String toString() {
return MoreObjects.toStringHelper(this)
.addValue(
IntStream.range(0, marked.length)
.filter(this::marked)
.boxed()
.collect(Collectors.toList()))
.toString();
}
}

Proposition: DFS marks all the vertices in a digraph reachable from a give set of sources in time proportional to the sum of the outdegrees of the vertices marked.

Application: Mark-and-sweep garbage collection.

Questions:

Single-source directed paths: Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v? If so, find such a path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class DepthFirstDirectedPaths {
private boolean[] marked;
private int[] edgeTo;
private final int source;
public DepthFirstDirectedPaths(Digraph graph, int source) {
this.marked = new boolean[graph.getVerticesCount()];
this.edgeTo = new int[graph.getVerticesCount()];
this.source = source;
doDfs(graph, source);
}
private void doDfs(Digraph graph, int v) {
marked[v] = true;
for (int w : graph.adjacentVertices(v)) {
if (!marked[w]) {
edgeTo[w] = v;
doDfs(graph, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public List<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
List<Integer> vertices = new ArrayList<>();
for (int x = v; x != source; x = edgeTo[x]) {
vertices.add(x);
}
vertices.add(source);
Collections.reverse(vertices);
return vertices;
}
}

Single-source shortest directed paths: Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v? If so, find a shortest such path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class BreathFirstDirectedPaths {
private boolean[] marked;
private int[] edgeTo;
private final int source;
public BreathFirstDirectedPaths(Digraph digraph, int source) {
this.marked = new boolean[digraph.getVerticesCount()];
this.edgeTo = new int[digraph.getVerticesCount()];
this.source = source;
doBfs(digraph, source);
}
private void doBfs(Digraph digraph, int s) {
Queue<Integer> queue = new ArrayDeque<>();
marked[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : digraph.adjacentVertices(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.add(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public List<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
List<Integer> result = new ArrayList<>();
for (int x = v; x != source; x = edgeTo[x]) {
result.add(x);
}
result.add(source);
Collections.reverse(result);
return result;
}
}

Cycles and DAGs

Directed Cycle Detection

Directed cycle detection: Does a given digraph have a directed cycle? If so, find the vertices on some such cycle, in order from some vertex back to itself.

Definition: A directed acyclic graph (DAG) is a graph with no directed cycles.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class DirectedCycle {
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle; // vertices on a cycle (if one exists)
private boolean[] onStack; // vertices on recursive call stack
public DirectedCycle(Digraph digraph) {
this.marked = new boolean[digraph.getVerticesCount()];
this.edgeTo = new int[digraph.getVerticesCount()];
this.onStack = new boolean[digraph.getVerticesCount()];
for (int v = 0; v < digraph.getVerticesCount(); v++) {
if (!marked[v]) {
doDfs(digraph, v);
}
}
}
private void doDfs(Digraph digraph, int v) {
onStack[v] = true;
marked[v] = true;
for (int w : digraph.adjacentVertices(v)) {
if (hasCycle()) {
return;
} else if (!marked[w]) {
edgeTo[w] = v;
doDfs(digraph, w);
} else if (onStack[w]) {
cycle = new Stack<>();
for (int x = v; x != w; x = edgeTo[x]) {
cycle.push(x);
}
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;
}
public boolean hasCycle() {
return cycle != null;
}
public List<Integer> cycle() {
return cycle;
}
}

When executing doDfs(digraph, v), we have followed a directed path from the source to v. To keep track of this path, DirectedCycle maintains a vertex-indexed array on onStack[] that marks the vertices on the recursive call stack (by setting onStack[v] to true on entry to doDfs(digraph, v) and to false on exit). DirectedCycle also maintains an edgeTo[] array so that it can return the cycle when it is detected.

Depth-first orders and topological sort

Precedence-constrained scheduling amounts to computing a topological order for the vertices of a DAG:

1
2
3
Topological(Digraph G)
boolean isDAG()
Iterable<Integer> order()

Proposition: A digraph has a topological order if and only if it is a DAG.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class DepthFirstOrder {
private boolean[] marked;
private List<Integer> pre;
private List<Integer> post;
private List<Integer> reversePost;
public DepthFirstOrder(Digraph digraph) {
this.marked = new boolean[digraph.getVerticesCount()];
this.pre = new ArrayList<>();
this.post = new ArrayList<>();
this.reversePost = new ArrayList<>();
for (int v = 0; v < digraph.getVerticesCount(); v++) {
if (!marked[v]) {
doDfs(digraph, v);
}
}
Collections.reverse(this.reversePost);
}
private void doDfs(Digraph digraph, int v) {
pre.add(v);
marked[v] = true;
for (int w : digraph.adjacentVertices(v)) {
if (!marked[w]) {
doDfs(digraph, w);
}
}
post.add(v);
reversePost.add(v);
}
public Iterable<Integer> preorder() {
return pre;
}
public Iterable<Integer> postorder() {
return post;
}
public Iterable<Integer> reversePostorder() {
return reversePost;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Topological {
private Iterable<Integer> order;
public Topological(Digraph digraph) {
DirectedCycle cycleFinder = new DirectedCycle(digraph);
if (!cycleFinder.hasCycle()) {
DepthFirstOrder dfs = new DepthFirstOrder(digraph);
order = dfs.reversePostorder();
}
}
public Iterable<Integer> order() {
return order;
}
public boolean isDag() {
return order != null;
}
}

Proposition: Reverse postorder in a DAG is a topological sort.

Proposition: With DFS, we can topologically sort a DAG in time proportional to V + E.

Strong connectivity in digraphs

Definition: Two vertice v and w are strongly connected if they are mutually reachable: that is, if there is a directed path from v to w and a directed path from w to v. A digraph is strongly connected if all its vertices are strongly connected to each other.

It is easy to see that two vertices are strongly connected if and only if there exists a general directed cycle that contains them both.

Strong components: Like connectivity in undirected graphs, strong connectivity in digraphs is an equivalence relation on the set of vertices, as it has the following properties:

  • Reflexive: Every vertex v is strongly connected to itself
  • Symmetric: If v is strongly connected to w, then w is strongly connected to v
  • Transitive: If v is strongly connected to w and w is strongly connected to x, then v is also strongly connected to x

API:

1
2
3
4
StronglyConnectedComponent(Digraph digraph)
boolean stronglyConnected(int v, int w)
int count()
int id(int v)

Kosaraju-Sharir algorithm

  • Given a digraph G, use DepthFirstOrder to compute the reverse postorder of its reverse digraph GR
  • Run standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerical order
  • All vertices visited on a call to the recursive dfs() from the constructor are a strong component
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class StronglyConnectedComponent {
private boolean[] marked;
private int[] id;
private int count;
public StronglyConnectedComponent(Digraph digraph) {
this.marked = new boolean[digraph.getVerticesCount()];
this.id = new int[digraph.getVerticesCount()];
DepthFirstOrder order = new DepthFirstOrder(digraph.reverse());
for (int s : order.reversePostorder()) {
if (!marked[s]) {
doDfs(digraph, s);
count++;
}
}
}
private void doDfs(Digraph digraph, int v) {
marked[v] = true;
id[v] = count;
for (int w : digraph.adjacentVertices(v)) {
if (!marked[w]) {
doDfs(digraph, w);
}
}
}
public boolean stronglyConnected(int v, int w) {
return id[v] == id[w];
}
public int id(int v) {
return id[v];
}
public int count() {
return count;
}
public Map<Integer, List<Integer>> strongComponents() {
return IntStream.range(0, id.length).boxed().collect(Collectors.groupingBy(this::id));
}
}

Proposition: The Kosaraju-Sharir algorithm uses preprocessing time and space proportional to V + E to support constant-time strong connectivity queries in a diagraph.

Reachability revisited

What about pairs of vertices that are not strongly connected? There may be a path from v to w or a path from w to v, but not both

All-pairs reachability: Given a digraph, support queries of the form Is there a directed path from a given vertex v to another given vertex w?

For undirected graphs, the corresponding problem is equivalent to the connectivity problem; for digraphs, it is quite different from the strong connectivity problem.

Definition: The transitive closure of a digraph G is another digraph with the same set of vertices, but with an edge from v to w in the transitive closure if and only if w is reachable from v in G.

API:

1
2
TransitiveClosure(Digraph G)
boolean reachable(int v, int w)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class TransitiveClosure {
private DirectedDfs[] all;
public TransitiveClosure(Digraph digraph) {
all = new DirectedDfs[digraph.getVerticesCount()];
for (int v = 0; v < digraph.getVerticesCount(); v++) {
all[v] = new DirectedDfs(digraph, v);
}
}
public boolean reachable(int v, int w) {
return all[v].marked(w);
}
}

The above solution is ideal for small or dense digraphs, but it is not a solution for the large digraphs we might encounter in practice because the constructor uses space proportional to V^2 and time proportional to V(V+E).

A general solution that achieves constant-time queries with substantially less than quadratic space is an unsolved research problem, with important practical implications.

Minimum Spanning Trees

An edge-weighted graph is a graph model where we associate weights or costs with each edge.

Definition: Recall that a spanning tree of a graph is a connected subgraph with no cycles that includes all the vertices. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.

Assumptions:

  • The graph is connected
  • The edge weights are not necessarily distances
  • The edge weights may be zero or negative
  • The edge weights are all different (this assumption is not restrictive because our algorithms work without modification in the presence of equal weights)

Underlying principles

  • Adding an edge that connects two vertices in a tree creates a unique cycle
  • Removing an edge from a tree breaks it into two separate subtrees

Cut property: This property, which we refer to as the cut property, has to do with identifying edges that must be in the MST of a given edge-weighted graph, by dividing vertices into two sets and examining edges that cross the division.

Definition: A cut of a graph is a partition of its vertices into two nonempty disjoint sets. A crossing edge of a cut is an edge that connects a vertex in one set with a vertex in the other.

Proposition (Cut property) Given any cut in an edge-weighted graph, the crossing edge of minimum weight is in the MST of the graph.

Proposition (Greedy MST algorithm) The following method colors black all edges in the MST of any connected edge-weighted graph with V vertices: starting with all edges colored gray, find a cut with no black edges, color its minimum-weight edge black, and continue until V - 1 edges have been colored black.

Edge-weighted graph data type

1
2
3
4
Edge(int v, int w, double weight)
int either()
int other(int v)
int compareTo(Edge that)

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Edge implements Comparable<Edge> {
private final int v;
private final int w;
private final double weight;
public Edge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
public int either() {
return v;
}
public int other(int vertex) {
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new RuntimeException("Inconsistent edge!");
}
public double getWeight() {
return weight;
}
@Override
public int compareTo(Edge that) {
return Double.compare(this.weight, that.weight);
}
@Override
public boolean equals(Object that) {
if (this == that) {
return true;
}
if (that instanceof Edge) {
Edge thatEdge = (Edge) that;
return this.v == thatEdge.v
&& this.w == thatEdge.w
&& Double.compare(this.weight, thatEdge.weight) == 0;
}
return false;
}
@Override
public int hashCode() {
return Objects.hash(v, w, weight);
}
@Override
public String toString() {
return String.format("%d-%d %.5f", v, w, weight);
}
}
1
2
3
4
5
6
EdgeWeightedGraph(int V)
int V()
int E()
void addEdge(Edge e)
Iterable<Edge> adj(int v)
Iterable<Edge> edges()

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class EdgeWeightedGraph {
private final int verticesCount;
private int edgesCount;
private Set<Edge>[] adjacencyEdgeList;
public EdgeWeightedGraph(int verticesCount) {
this.verticesCount = verticesCount;
this.edgesCount = 0;
this.adjacencyEdgeList = (Set<Edge>[]) new Set[verticesCount];
for (int v = 0; v < verticesCount; v++) {
adjacencyEdgeList[v] = new TreeSet<>();
}
}
public int verticesCount() {
return verticesCount;
}
public int edgesCount() {
return edgesCount;
}
public void addEdge(Edge edge) {
int v = edge.either();
int w = edge.other(v);
adjacencyEdgeList[v].add(edge);
adjacencyEdgeList[w].add(edge);
edgesCount++;
}
public Set<Edge> adjacencyEdges(int v) {
return adjacencyEdgeList[v];
}
public Set<Edge> edges() {
Set<Edge> edges = new TreeSet<>();
for (int v = 0; v < verticesCount; v++) {
for (Edge edge : adjacencyEdgeList[v]) {
if (edge.other(v) > v) {
edges.add(edge);
}
}
}
return edges;
}
}

MST API and test client

1
2
3
MST(EdgeWeightedGraph G)
Iterable<Edge> edges
double weight()

Test Data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static final EdgeWeightedGraph SAMPLE_WEIGHTED_GRAPH;
static {
SAMPLE_WEIGHTED_GRAPH =
new EdgeWeightedGraph(8)
.addEdge(new Edge(4, 5, .35))
.addEdge(new Edge(4, 7, .37))
.addEdge(new Edge(5, 7, .28))
.addEdge(new Edge(0, 7, .16))
.addEdge(new Edge(1, 5, .32))
.addEdge(new Edge(0, 4, .38))
.addEdge(new Edge(2, 3, .17))
.addEdge(new Edge(1, 7, .19))
.addEdge(new Edge(0, 2, .26))
.addEdge(new Edge(1, 2, .36))
.addEdge(new Edge(1, 3, .29))
.addEdge(new Edge(2, 7, .34))
.addEdge(new Edge(6, 2, .40))
.addEdge(new Edge(3, 6, .52))
.addEdge(new Edge(6, 0, .58))
.addEdge(new Edge(6, 4, .93));
}

Prim’s algorithm

Prim’s algorithm, is to attach a new edge to a single growing tree at each step. Start with any vertex as a single-vertex tree, than add V - 1 edges to it, always taking next (coloring black) the minimum weight edge that connects a vertex on the tree to a vertex not yet on the tree (a crossing edge for the cut defined by tree vertices).

Proposition Prim’s algorithm computes the MST of any connected edge-weighted graph.

Data structures: We implement Prim’s algorithm with the aid of a few simple and familiar data strucutres:

  • Vertices on the tree: We use a vertex-indexed boolean array marked[], where marked[v] is true if v is on the tree
  • Edges in the tree: We use one of two data structures: either a queue mst to collect edges in the MST or a vertex-indexed array edgeTo[] of Edge objects, where edgeTo[v] is the Edge that connects v to the tree
  • Crossing edges: We use a MinPQ<Edge> priority queue that compares edges by weight

Maintaining the set of crossing edges Each time we add an edge to the tree, we also add a vertex to the tree. To maintain the set of crossing edges, we need to add to the priority queue all edges from that vertex to any non-tree vertex (using marked[] to identify such edges). Bu we must do more: any edge connecting the vertex just added to a tree vertex that is already on the priority queue now becomes ineligible (it is no longer a crossing edge because it connects two tree vertices).

Lazy version of Prim’s algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class LazyPrimMst {
private boolean[] marked;
private List<Edge> mst;
private TreeSet<Edge> priorityQueue;
public LazyPrimMst(EdgeWeightedGraph graph) {
this.priorityQueue = new TreeSet<>();
this.marked = new boolean[graph.verticesCount()];
this.mst = new ArrayList<>();
visit(graph, 0); // Assume graph is connected
while (!priorityQueue.isEmpty()) {
Edge minEdge = priorityQueue.pollFirst();
int v = minEdge.either();
int w = minEdge.other(v);
// Skip if the edge is ineligible
if (marked[v] && marked[w]) {
continue;
}
mst.add(minEdge);
if (!marked[v]) visit(graph, v);
if (!marked[w]) visit(graph, w);
}
}
private void visit(EdgeWeightedGraph graph, int v) {
marked[v] = true;
for (Edge e : graph.adjacencyEdges(v)) {
if (!marked[e.other(v)]) {
priorityQueue.add(e);
}
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return mst.stream().mapToDouble(Edge::getWeight).sum();
}
}

Proposition The lazy version of Prim’s algorithm uses space proportional to E and time proportional to ElogE (in the worst case) to compute the MST of a connected edge-weighted graph with E edges and V vertices.

Eager version of Prim’s algorithm

To improve the LazyPrimMst, we might try to delete ineligible edges from the priority queue, so that the priority queue contains only the crossing edges between tree vertices and non-tree vertices.

But we can eliminate even more edges. The key is to note that our only interest is in the minimal edge from each non-tree vertex to a tree vertex. When we add a vertex v to the tree, the only possible change with respect to each non-tree vertex w is that adding v brings w closer than before to the tree.

In short, we do not need to keep on the priority queue all of the edges from w to tree vertices - we just need to keep track of the minimum-weight edge and check whether the addition of v to the tree necessiates that we update that minimum (because of an edge v-w that has lower weight), which we can do as we process each edge in v‘s adjacency list.

In other words, we maintain on the priority queue just one edge for each non-tree vertex w: the lightest edge that connects it to the tree. Any heavier edge connecting w to the tree will become ineligible at some point, so there is no need to keep it on the priority queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class PrimMst {
private Edge[] edgeTo;
private double[] distTo;
private boolean[] marked;
private IndexMinPQ<Double> priorityQueue;
public PrimMst(EdgeWeightedGraph graph) {
this.edgeTo = new Edge[graph.verticesCount()];
this.distTo = new double[graph.verticesCount()];
this.marked = new boolean[graph.verticesCount()];
for (int v = 0; v < graph.verticesCount(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
priorityQueue = new IndexMinPQ<>(graph.verticesCount());
distTo[0] = 0.0;
priorityQueue.insert(0, 0.0);
while (!priorityQueue.isEmpty()) {
visit(graph, priorityQueue.delMin());
}
}
private void visit(EdgeWeightedGraph graph, int v) {
marked[v] = true;
for (Edge e : graph.adjacencyEdges(v)) {
int w = e.other(v);
if (marked[w]) continue;
if (e.weight() < distTo[w]) {
// e is the new best connection from tree to w
edgeTo[w] = e;
distTo[w] = e.weight();
if (priorityQueue.contains(w)) {
priorityQueue.changeKey(w, distTo[w]);
} else {
priorityQueue.insert(w, distTo[w]);
}
}
}
}
public List<Edge> edges() {
List<Edge> edges = new ArrayList<>();
for (int v = 0; v < edgeTo.length; v++) {
Edge e = edgeTo[v];
if (e != null) {
edges.add(e);
}
}
return edges;
}
}

Proposition The eager version of Prim’s algorithm uses extra space proportional to V and time proportional to ElogV (in the worst case) to compute the MST of a connected edge-weighted graph with E edges and V vertices.

Kruskal’s algorithm

Kruskal’s algorithm is to process the edges in order of their weight values (smallest to largest), taking for the MST (coloring black) each edge that does not form a cycle with edges previously added, stopping after adding V - 1 edges.

Proposition Kruskal’s algorithm computes the MST of any connected edge-weighted graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class KruskalMst {
private List<Edge> mst;
public KruskalMst(EdgeWeightedGraph graph) {
this.mst = new ArrayList<>();
TreeSet<Edge> sortedEdges = new TreeSet<>(graph.edges());
UnionFind uf = new UnionFind(graph.verticesCount());
while (!sortedEdges.isEmpty() && mst.size() < graph.verticesCount() - 1) {
Edge e = sortedEdges.pollFirst();
int v = e.either();
int w = e.other(v);
if (uf.connected(v, w)) continue;
uf.union(v, w);
mst.add(e);
}
}
public List<Edge> edges() {
return mst;
}
}

Proposition Kruskal’s algorithm uses space proportional to E and time proportional to ElogE (in the worst case) to compute the MST of an edge-weighted connected graph with E edges and V vertices.

Perspective

1
2
3
4
5
6
7
algorithm space time
lazy Prim E ElogE
eager Prim V ElogV
Kruskal E ElogE
Fredman-Tarjan V E+VlogV
Chazelle V very, very nearly, but not quite E

No theorectical results have been developed that deny the existence of an MST algorithm that is guaranteed to run in linear time for all graphs. On the other hand, the goal of developing algorithms for computing the MST of sparse graphs in linear time remains elusive.

Shortest Paths

The possibility of one-way roads means that we will need to consider edge-weighted digraphs. In this model, this problem is easy to formulate:

Find a lowest-cost way to get from one vertex to another.

Definition A shortest path from vertex s to vertex t in an edge-weighted digraph is a directed path from s to t with the propertythat no other such path has a lower weight.

Single-source shortest paths Given an edge-weighted digraph and a source vertex sm support queries of the form Is there a directed path from s to a given target vertex t? If so, find a shortest such path (one whose total weight is minimal)

This section will cover:

  • APIs and implementations for edge-weighted digraphs, and a single-source shortest-paths API
  • The classic Dijkstra’s algorithm for the problem when weights are nonnegative
  • A faster algorithm for acyclic edge-weighted digraphs (edge-weighted DAGs) that works even when edge weights can be negative
  • The classic Bellman-Ford algorithm for use in the general case, when cycles may be present, edge weights may be negative, and we need algorithms for finding negative-weight cycles and shortest paths in edge-weighted digraphs with no such cycles

Propperties of shortest paths:

  • Paths are directed
  • The weights are not necessarily distances
  • Not all vertices need be reachable
  • Negative weights introduce complications
  • Shortest paths are normally simple
  • Shortest paths are not necessarily unique
  • Parallel edges and self-loop may be present

Definition Given an edge-weighted digraph and a designated source vertex s, a shortest-paths tree for vertex s is a subgraph containing s and all the vertices reachable from s that forms a directed tree rooted at s such that every tree path is a shortest path in the digraph.

Edge-weighted digraph data types

1
2
3
4
DirectedEdge(int v, int w, double weight)
double weight()
int from()
int to()

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class DirectedEdge {
private final int from;
private final int to;
private final double weight;
public DirectedEdge(int from, int to, double weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public int from() {
return from;
}
public int to() {
return to;
}
public double weight() {
return weight;
}
@Override
public String toString() {
return String.format("%d->%d %.2f", from, to, weight);
}
}
1
2
3
4
5
6
EdgeWeightedDigraph(int V)
int V()
int E()
void addEdge(DirectedEdge e)
Iterable<DirectedEdge> adj(int v)
Iterable<DirectedEdge> edges()

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class EdgeWeightedDigraph {
private final int verticesCount;
private int edgesCount;
private List<DirectedEdge>[] adjacencyLists;
public EdgeWeightedDigraph(int verticesCount) {
this.verticesCount = verticesCount;
this.edgesCount = 0;
this.adjacencyLists = (List<DirectedEdge>[]) new List[verticesCount];
for (int v = 0; v < verticesCount; v++) {
this.adjacencyLists[v] = new ArrayList<>();
}
}
public int verticesCount() {
return verticesCount;
}
public int edgesCount() {
return edgesCount;
}
public void addEdge(DirectedEdge e) {
adjacencyLists[e.from()].add(e);
edgesCount++;
}
public List<DirectedEdge> adjacencyEdges(int v) {
return adjacencyLists[v];
}
public List<DirectedEdge> edges() {
List<DirectedEdge> edges = new ArrayList<>();
for (int v = 0; v < verticesCount; v++) {
edges.addAll(adjacencyLists[v]);
}
return edges;
}
@Override
public String toString() {
return Joiner.on("\r\n").join(edges());
}
}

Shortest-paths API:

1
2
3
4
ShortestPath(EdgeWeightedDigraph graph, int s)
double distTo(int v)
boolean hasPathTo(int v)
Iterable<DirectedEdge> pathTo(int v)

Data structures for shortest paths

  • Edges on the shortest-path tree: As for DFS, BFS, and Prim’s algorithm, we use a parent-edge representation in the form of a vertex-indexed array edgeTo[] of DirectedEdge objects, where edgeTo[v] is the edge that connects v to its parent in the tree
  • Distance to the source: We use a vertex-indexed array distTo[] such that distTo[v] is the length of the shortest known path from s to v

By convention, edgeTo[s] is null and distTo[s] is 0. We also adopt the convention that distances to vertices that are not reachable from the source are all Double.POSITIVE_INFINITY.

Edge relaxation To relax an edge v->w means to test whether the best known way from s to w is to go from s to v, then take the edge from v to w, if so, update data structure to indicate that to be the case.

1
2
3
4
5
6
7
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}

Vertex relaxation All of our implementations actually relax all the edges pointing from a given vertex as shown in the (overloaded) implementation of relax() below.

1
2
3
4
5
6
7
8
9
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
}

Theoretical basis for shortest-paths algorithms

Proposition (Shortest-paths optimality conditions) Let G be an edge-weighted digraph, with s a source vertex in G and distTo[] a vertex-indexed array of path lengths in G such that, for all v reachable from s, the value of distTo[v] is the length of some path from s to v with distTo[v] equal to infinity for all v not reachable from s. These values are the lengths of shortest paths if and only if they satisfy distTo[s] = 0 and distTo[w] <= distTo[v] + e.weight() for each edge e from v or w.

Proposition (Generic shortest-paths algorithm) Initialize distTo[s] to 0 and all other distTo[] values to infinity, and proceed as follows:

Relax any edge in G, continuing until no edge is eligible

For all vertices w reachable from s, the value of distTo[w] after this computation is the length of a shortest path from s to w (and edgeTo[w] is the last edge on such a path)

Dijkstra’s algorithm

We begin by initializing distTo[s] to 0 and all other distTo[] entries to positive infinity, then we relax and add to the tree a non-tree vertex with the lowest distTo value, continuing untill all vertices are on the tree or no non-tree vertex has a finite distTo value.

Data structures To implement Dijkstra’s algorithm we add to our distTo[] and edgeTo[] data structures an index priority queue pq to keep track of vertices that are candidates for being the next to be relaxed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class DijkstraShortestPath {
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;
public DijkstraShortestPath(EdgeWeightedDigraph graph, int s) {
this.edgeTo = new DirectedEdge[graph.verticesCount()];
this.distTo = new double[graph.verticesCount()];
this.pq = new IndexMinPQ<>(graph.verticesCount());
for (int v = 0; v < graph.verticesCount(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
pq.insert(s, 0.0);
while (!pq.isEmpty()) {
relax(graph, pq.delMin());
}
}
private void relax(EdgeWeightedDigraph graph, int v) {
for (DirectedEdge e : graph.adjacencyEdges(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) {
pq.changeKey(w, distTo[w]);
} else {
pq.insert(w, distTo[w]);
}
}
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
public List<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
List<DirectedEdge> path = new ArrayList<>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.add(e);
}
Collections.reverse(path);
return path;
}
}

Proposition Dijkstra’s algorithm use extra space proportional to V and time proportional to ElogV (in the worst case) to solve the single-source shortest paths problem in an edge-weighted digraph with E edges and V vertices.

Variants:

  • Single-source shortest paths in undirected graphs
  • Source-sink shortest paths
  • All-pairs shortest paths
  • Shortest paths in Euclidean graphs

Acyclic edge-weighted digraphs

We now consider an algorithm for finding shortest paths that is simpler and faster than Dijkstra’s algorithm for edge-weighted DAGs. Specifically, it

  • Solves the single-source problem in linear time
  • Handles negative edge weights
  • Solves related problems, such as finding longest paths

These algorithms are straightforward extensions to the algorithm for topological sort in DAGs.

Specifically, vertex relaxation, in combination with topological sorting, immediately presents a solution to the single-source-shortest-paths problem for edge-weighted DAGs. We initialize distTo[s] to 0 and all other dist[] values to infinity, then relax the vertices, one by one, taking the vertices in topological order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class AcyclicShortestPath {
private DirectedEdge[] edgeTo;
private double[] distTo;
public AcyclicShortestPath(EdgeWeightedDigraph digraph, int s) {
this.edgeTo = new DirectedEdge[digraph.verticesCount()];
this.distTo = new double[digraph.verticesCount()];
for (int v = 0; v < digraph.verticesCount(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
EWTopological topological = new EWTopological(digraph);
for (int v : topological.order()) {
relax(digraph, v);
}
}
private void relax(EdgeWeightedDigraph digraph, int v) {
for (DirectedEdge edge : digraph.adjacencyEdges(v)) {
int w = edge.to();
if (distTo[w] > distTo[v] + edge.weight()) {
distTo[w] = distTo[v] + edge.weight();
edgeTo[w] = edge;
}
}
}
public double distTo(int v) {
return distTo[v];
}
public boolean hasPathTo(int v) {
return edgeTo[v] == null;
}
public List<DirectedEdge> pathTo(int v) {
List<DirectedEdge> result = new ArrayList<>();
for (DirectedEdge edge = edgeTo[v]; edge != null; edge = edgeTo[edge.from()]) {
result.add(edge);
}
Collections.reverse(result);
return result;
}
}

Proposition By relaxing vertices in topological order, we can solve the single-source shortest-paths problem for edge-weighted DAGs in time proportional to E + V.

Longest paths

Single-source longest paths in edge-weighted DAGs Given an edge-weighted DAG (with negative weights allowed) and a source vertex s, support queries of the form: Is there a directed path from s to a given target vertex v? If so, find a longest such path.

Proposition We can solve the longest-paths problem in edge-weighted DAGs in time proportional to E + V.

Parallel job scheduling

Parallel precedence-constrained scheduling Given a set of jobs of specified duration to be completed, with precedence constraints that specify that certain jobs have to be completed before certain other jobs are begun, how can we schedule the jobs on identical processors (as many as needed) such that they are all completed in the minimum amount of time while still respecting the constraints?

Remarkably, a linear-time algorithm is available - an approach known as the critical path method demonstrates that the problem is equivalent to a longest-pathss problem in an edge-weighted DAG.

Shortest paths in general edge-weighted digraphs

What if the digraph has negative-weight edges?

Definition A negative cycle in an edge-weighted digraph is a directed cycle whose total weight (sum of the weights of its edges) is negative.

Proposition There exists a shortest path from s to v in an edge-weighted digraph if and only if there exists at least one directed path from s to v and no vertex on any directed path from s to v is on a negative cycle.

Two important problems

Negative cycle detection Does a given edge-weighted digraph have a negative cycle? If it does, find one such cycle.

Single-source shortest paths when nagative cycles are not reachable Given an edge-weighted digraph and a source s with no negative cycles reachable from s, support queries of the form Is their a directed path from s to a given target vertex v? If so, find a shortest such path.

Bellman-Ford algorithm

Proposition (Bellman-Ford algorithm) The following method solves the single-source shortest-paths problem from a given source s for any edge-weighted digraph with V vertices and no negative cycles reachable from s: Initialize distTo[s] to 0 and all other distTo[] values to infinity. Then considering the digraph’s edges in any order, relax all edges. Make V such pass.

Proposition The Bellman-Ford algorithm takes time proportional to EV and extra space proportional to V.

1
2
3
4
5
6
7
for (int pass = 0; pass < G.V(); pass++) {
for (v = 0; v < G.V(); v++) {
for (DirectedEdge e : G.adj(v)) {
relax(e);
}
}
}

We do not consider this version in detail because it always relaxes VE edges, and a simple modification makes the algorithm much more efficient for typical applications.

Queue-based Bellman-Ford

Specifically, we can easily determine a priori that numerous edges are not going to lead to a sucessful relaxation in any given pass: the only edges that could lead to a change in distTo[] are thoseleaving a vertex whose distTo[] value changed in the previous pass. To keep track of such vertices, we use a FIFO queue.

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class BellmanFordShortestPath {
private double[] distTo; // length of path to v
private DirectedEdge[] edgeTo; // last edge on path to v
private boolean[] onQueue; // whether this vertex is on the queue
private Queue<Integer> queue; // vertices being relaxed
private int cost; // number of calls to relax()
private Iterable<Integer> cycle; // negative cycle in edgeTo[]?
public BellmanFordShortestPath(EdgeWeightedDigraph digraph, int s) {
this.distTo = new double[digraph.verticesCount()];
this.edgeTo = new DirectedEdge[digraph.verticesCount()];
this.onQueue = new boolean[digraph.verticesCount()];
this.queue = new ArrayDeque<>();
for (int v = 0; v < digraph.verticesCount(); v++) {
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;
queue.offer(s);
onQueue[s] = true;
while (!queue.isEmpty() && !hasNegativeCycle()) {
int v = queue.poll();
onQueue[v] = true;
relax(digraph, v);
}
}
private void relax(EdgeWeightedDigraph digraph, int v) {
for (DirectedEdge edge : digraph.adjacencyEdges(v)) {
int w = edge.to();
if (distTo[w] > distTo[v] + edge.weight()) {
distTo[w] = distTo[v] + edge.weight();
edgeTo[w] = edge;
if (!onQueue[w]) {
queue.offer(w);
onQueue[w] = true;
}
}
if (cost++ % digraph.verticesCount() == 0) {
findNegativeCycle();
}
}
}
private void findNegativeCycle() {
int verticeCount = edgeTo.length;
EdgeWeightedDigraph digraph = new EdgeWeightedDigraph(verticeCount);
for (DirectedEdge anEdgeTo : edgeTo) {
if (anEdgeTo != null) {
digraph.addEdge(anEdgeTo);
}
}
EWDirectedCycle cycleFinder = new EWDirectedCycle(digraph);
cycle = cycleFinder.cycle();
}
public boolean hasNegativeCycle() {
return cycle != null;
}
public Iterable<Integer> negativeCycle() {
return cycle;
}
}

Proposition The queue-based implementation of the Bellman-Ford algorithm solves the single souce shortest-paths problem from a given source s (or finds a negative cycle reachable from s) for any edge-weighted digraph with E edges and V vertices, in time proportional to EV and extra space proportional to V, in the worst case.

Proof If there is no negative cycle reachable from s, the algorithm terminates after relaxation corresponding to the (V - 1)st pass of the generic algorithm (since all shortest paths have fewer than V edges). If there does exist a negative cycle reachable from s, the queue never empties. If any edge is relaxed during the Vth pass of the generic algorithm, then the edgeTo[] array has a directed cycle and such cycle is a negative cycle.

Arbitrage

Proposition The arbitrage problem is a negative-cycle-detection problem in edge-weighted digraphs.

Proof Replace each weight by its logarithm, negated. With this change, computing path weights by multiplying edge weights edge weights in the original problem corresponds to adding them in the transformed problem. Specifically, any product w1w2...wk corresponds to a sum -ln(w1)-ln(w2)-...-ln(wk). The transformed edge weights might be negative or positive, a path from v to w gives a way of converting from currency v to currency w, and any negative cycle is an arbitrage opportunity.