1 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 ∞ -

2 ∞ -

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

5

1

Fringe: [(1: ∞), (2: ∞), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

0

∞

1

h(v, goal)

1

3

15

1

∞

0

h(v, goal) is arbitrary. In this example, it’s the min weight edge out of each vertex.

datastructur.es

2 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

5

1

Fringe: [(1: 5), (2: 16), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

0

∞

1

2

1

h(v, goal)

1

3

15

1

∞

0

datastructur.es

3 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 ∞ -

4 ∞ -

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

5

1

Fringe: [(2: 16), (3: ∞), (4: ∞), (5: ∞), (6: ∞)]

4

0

∞

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

datastructur.es

4 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 13 1

4 5 1

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

5

1

Fringe: [(4: 6), (3: 15), (2: 16), (5: ∞), (6: ∞)]

4

0

∞

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

5

13

Which vertex is removed next?

datastructur.es

5 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

Give distTo, edgeTo, and fringe after relaxation

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 13 1

4 5 1

5 ∞ -

6 ∞ -

5

2

1

15

3

2

11

5

1

Fringe: [(3: 15), (2: 16), (5: ∞), (6: ∞)]

4

0

∞

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

5

13

datastructur.es

6 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

Give distTo, edgeTo, and fringe after relaxation

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 13 1

4 5 1

5 9 4

6 10 4

5

2

1

15

3

2

11

5

1

Fringe: [(6: 10), (3: 15), (2: 16), (5: ∞)]

4

0

∞

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

5

13

10

9

datastructur.es

7 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 13 1

4 5 1

5 9 4

6 10 4

5

2

1

15

3

2

11

5

1

Fringe: [(6: 10), (3: 15), (2: 16), (5: ∞)]

4

0

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

5

13

10

9

Next vertex to be dequeued is our target, so we’re done!

datastructur.es

8 of 8

A* Demo, with s = 0, goal = 6.

Insert all vertices into fringe PQ, storing vertices in order of d(source, v) + h(v, goal).

Repeat: Remove best vertex v from PQ, and relax all edges pointing from v.

1

2

3

4

5

6

0

s

# distTo edgeTo

0 0 -

1 2 0

2 1 0

3 13 1

4 5 1

5 9 4

6 10 4

5

2

1

15

3

2

11

5

1

4

0

1

h(v, goal)

1

3

15

2

1

∞

0

1

2

5

13

10

9

Observations:

Not every vertex got visited.
Result is not a shortest paths tree for vertex zero (path to 3 is suboptimal!), but that’s OK because we only care about path to 6.

datastructur.es