1 of 12

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

1

1

6

1

-20

1

1

1

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

0

∞

∞

∞

∞

∞

2 of 12

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

1

1

6

1

-20

1

1

1

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

0

∞

∞

∞

∞

∞

3 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 ∞ -

3 1 0

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

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

0

∞

∞

∞

∞

∞

1

1

4 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 ∞ -

3 1 0

4 ∞ -

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [1, 2, 4, 5]

0

∞

∞

∞

1

1

5 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 ∞ -

3 1 0

4 2 3

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [1, 2, 4, 5]

0

∞

∞

∞

1

1

2

6 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 ∞ -

3 1 0

4 2 3

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [2, 4, 5]

0

∞

∞

1

1

2

7 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 2 3

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [2, 4, 5]

0

∞

∞

1

1

7

2

8 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 2 3

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [4, 5]

0

∞

1

1

7

2

9 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 -13 2

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [4, 5]

0

∞

1

1

7

2

-13

8

10 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 -13 2

5 ∞ -

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [5]

0

1

1

7

-13

8

11 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 -13 2

5 -12 4

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: [5]

0

∞

1

1

7

-13

-12

12 of 12

DAG SPT Algorithm

Visit vertices in topological order.

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

# distTo edgeTo

0 0 -

1 1 0

2 7 1

3 1 0

4 -13 2

5 -12 4

1

3

2

4

5

0

s

1

1

6

1

-20

1

1

1

Fringe: []

0

1

1

7

-13

-12