DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 ∞ -

2 ∞ -

3 ∞ -

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [0, 3, 1, 2, 4, 5]

0

∞

∞

∞

∞

∞

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 ∞ -

2 ∞ -

3 ∞ -

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [0, 3, 1, 2, 4, 5]

0

∞

∞

∞

∞

∞

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 ∞ -

3 2 0

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [3, 1, 2, 4, 5]

0

∞

∞

∞

∞

∞

2

2

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 ∞ -

3 2 0

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [1, 2, 4, 5]

0

∞

∞

∞

2

2

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 ∞ -

3 2 0

4 5 3

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [1, 2, 4, 5]

0

∞

∞

∞

2

2

5

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 ∞ -

3 2 0

4 5 3

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [2, 4, 5]

0

∞

∞

2

2

5

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [2, 4, 5]

0

∞

∞

2

2

5

8

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 ∞ -

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [4, 5]

0

∞

2

2

5

8

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 9 2

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [4, 5]

0

∞

2

2

5

8

9

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 9 2

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [5]

0

2

2

5

8

9

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 6 4

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: [5]

0

2

2

5

8

9

6

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

# distTo edgeTo

0 0 -

1 2 0

2 8 1

3 2 0

4 5 3

5 6 4

1

3

2

4

5

0

s

4

2

6

1

1

2

3

1

Fringe: []

0

2

2

5

8

6