We were unable to load Disqus. If you are a moderator please see our troubleshooting guide.

[CG]jupoulton • 7 years ago

Neat!

Racso • 7 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 • 7 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