Racso • 6 years ago
Thanks!
Bongiwe Citwa • 4 years ago
Perfect illustration!!
Pete Tyldesley • 4 years ago
Brilliant explanation, thanks! This is the first explanation I've read on the internet that helped me understand it straight away.
Anonymous • 4 years ago
nicola • 6 years ago
In the path, you can use a dict to keep the best previous node.
For example, here, the dict is {"A":None,"B":"A","C":"D","D":"B","E":"A","F":"A","G":"A"}.
That means that "A" is the start node and that from "C", the best path comes from "D".
You can also show a table like this:
A | B | C | D | E | F | G | choice
-----------------------------------
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A
- | - | - | - | - | - | - | prev.
-----------------------------------
* | 5 | ∞ | ∞ | 4 | 3 | 5 | F
- | A | - | - | A | A | A | prev.
-----------------------------------
* | 5 | ∞ | ∞ | 4 | * | 5 | E
- | A | - | - | A | * | A | prev.
-----------------------------------
* | 5 | ∞ | ∞ | * | * | 5 | B
- | A | - | - | * | * | A | prev.
-----------------------------------
* | * | 10| 6 | * | * | 5 | G
- | * | B | B | * | * | A | prev.
-----------------------------------
* | * | 10| 6 | * | * | * | D
- | * | B | B | * | * | * | prev.
-----------------------------------
* | * | 9 | * | * | * | * | C
- | * | D | * | * | * | * | prev.
9
A-B-D-C
Neat!