Interactive Pathfinding : Dijkstra vs A* Search

Showing A* search and Dijkstra's algorithm to see how they find the optimal path from S to W.

Created by Sajjad Ahmed Niloy

The Graph

Reference Image

S6
B5
C8
D2
E5
F1
W0
1
4
2
3
5
2
4
3
1

Start

Click "Next Step" to begin the A* search algorithm from node S.

Step 1: Evaluate Node S

Calculations use f(n) = g(n) + h(n).

  • S → B: f(B) = g(1) + h(5) = 6
  • S → C: f(C) = g(4) + h(8) = 12

Decision: Node B has the lowest f-score.

Step 2: Evaluate Node B

  • S→B→D: g(D)=4. f(D)=4+h(2)=6
  • S→B→C: g(C)=3. f(C)=3+h(8)=11 (Update)

Decision: Node D has the lowest f-score.

Step 3: Evaluate Node D

  • S→B→D→F: g(F)=6. f(F)=6+h(1)=7
  • S→B→D→W: g(W)=8. f(W)=8+h(0)=8

Decision: Node F has the lowest f-score.

Step 4: Evaluate Node F

  • S→B→D→F→W: g(W)=7. f(W)=7+h(0)=7 (Update)

Decision: Node W has the lowest f-score.

Step 5: Goal Reached!

Final Path: S → B → D → F → W

Total Cost: 7

Start

Click "Next Step" to begin Dijkstra's algorithm from node S.

Step 1: Evaluate Node S

Calculations use f(n) = g(n) (cost from start).

  • S → B: f(B) = g(1) = 1
  • S → C: f(C) = g(4) = 4

Decision: Node B has the lowest f-score.

Step 2: Evaluate Node B

  • S→B→D: g(D)=4. f(D)=4
  • S→B→C: g(C)=3. f(C)=3 (Update)

Decision: Node C has the lowest f-score.

Step 3: Evaluate Node C

  • S→B→C→E: g(E)=8. f(E)=8

Decision: Node D now has the lowest f-score in the open list.

Step 4: Evaluate Node D

  • S→B→D→F: g(F)=6. f(F)=6
  • S→B→D→W: g(W)=8. f(W)=8

Decision: Node F has the lowest f-score.

Step 5: Evaluate Node F

  • S→B→D→F→W: g(W)=7. f(W)=7 (Update)

Decision: Node W now has the lowest f-score.

Step 6: Goal Reached!

Final Path: S → B → D → F → W

Total Cost: 7