• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Dijkstra algorithm (baby steps)

 
Ranch Foreman
Posts: 175
8
IntelliJ IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone!
After this discussion (graph theory post) I got Grokking algorithms, and trying to implement some classics. Starting with Dijkstra.
I attach a drawing of the graph, and the python code. Like you all know and I am trying to figure out, the code is supposed to go through all the nodes and find a way to go further "cheaper".



I get the below error:



Why do I get this error? Obviously the while loop should stop when the returned node is none?

If you wonder why everything is called "1", its because there is a second graph for testing purposes but I have an error with the first one .


Screenshot-2019-07-18-at-17.30.22.png
[Thumbnail for Screenshot-2019-07-18-at-17.30.22.png]
 
Rancher
Posts: 1173
16
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Disclaimer: I know approximately zero Python.

That being said...
If node comes back from find_cheapest_node() as None, won't using None as the index/key into graph[] cause an error?  Should that test be...



EDIT:
Now that I reread your post, I see you agree with me:

Obviously the while loop should stop when the returned node is none?



If the while loop should stop when node is None, then check node, not graph[node].
 
D.J. Quavern
Ranch Foreman
Posts: 175
8
IntelliJ IDE Firefox Browser Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you SO MUCH! And that solved it!

For someone who knows approximately zero about python, you surely have a hawk eye !

Second graph works also, and I get finish cost = 8, which is the right answer.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!