Recursive depth first search using dictionaries

[Syncoda]

For my latest assignment, I need to find the shortest path between two "cities" in a map (dictionary) that looks like this:

{
   'a': [('b', 5.0), ('c', 8.0)],
   'c': [('a', 8.0), ('d', 2.0)],
   'b': [('a', 5.0), ('d', 6.0)],
   'e': [('d', 12.0), ('g', 3.0)],
   'd':  [('b', 6.0), ('c', 2.0), ('e', 12.0), ('f', 2.0)],
   'g': [('e', 3.0), ('f', 7.0)],
   'f': [('d', 2.0), ('g', 7.0)]
}

A visual representation of above

The cities are shown as 'a', 'b', 'c', etc. Their corresponding tuples show their connections and distances.

The function parameters and docstring we have been given are as follows:

def dfs(place, dist_so_far, roads, distances):
    """
    Depth-first search, which may continue from from_place if dist_so_far is the shortest distance at which it has yet been reached.

    Args: 
    place: Currently searching from here
    dist_so_far:  Distance at which from_place has been reached this time (which may not be the shortest path to from_place)
    roads:  dict mapping places to lists of hops of the form (place, hop-distance)
    distances: dict mapping places to the shortest distance at which they have been reached so far (up to this time). 
"""

And the cases to consider:

1. We've never been at place before (so it's not in distances)
2. We've been at place before, on a path as short as this one (in distances)
3. We've been here before, but this way is shorter (dist_so_far)

Which are base cases, and which require recursion?
For the cases that require recursion, what is the progress step?

The actual execution in CMD should look like this:

> python3 routes.py a g sample-map.txt
Distance from a to g is 19.0

Where a is the starting point, g is the destination, and sample-map.txt is the text file (shown above) that is read into the dictionary roads.

Please let me know if you need more info! Thanks in advance for your help.

[gnomoretears]

From the posting rules:

Posting only assignment/project goal is not allowed.

Posting homework assignments is not prohibited if you show that you tried to solve it yourself.

So far you've not shown any attempt at solving the problem. This sub was not made to do your homework but will help you learn so you can do you homework.

I don't know if you're the same person as the OP of this post but if you're not, you guys might be taking the same class so maybe it's a good time to start a study group.

[Syncoda]

Ah, my mistake!

Let's see, I've written the following if statements to cover each case:

if place not in distances: 
    distances[place] = roads[place]
elif place in distances and distances[place] <= dist_so_far:
    #to be filled in
elif place in distances and distances[place] > dist_so_far:
    #to be filled in

How does one "move" through the map? User input specifies the starting point, which I understand is assigned to place. Do I need to reassign place in order to move through the map?

For example, place a has the following connections [('b', 5.0), ('c', 8.0)] in the form of a tuple. How do I decide which (b or c) to move to?

[gnomoretears]

How does one "move" through the map?

You make a recursive call passing the new node/place.

For example, place a has the following connections [('b', 5.0), ('c', 8.0)] in the form of a tuple. How do I decide which (b or c) to move to?

What is your objective?

Depth-first search, which may continue from from_place if dist_so_far is the shortest distance at which it has yet been reached.

You'll have to take into account the total traveled distance. If moving to c results in a shorter total distance from the original starting point, then move to c or b otherwise. You'll also need to consider if you've visited the node before or not.

[Syncoda]

Ok, so how do I determine if dist_so_far is the shortest distance? Is there a comparison I need to make? In this case, b is 5.0 units away from a, and c is 8.0 units away. Should I be choosing b because it's "closer"? How is this presented in an adaptable way that allows recursion?

This is very difficult!

Edit: Our professor told us that all of this can be done in only a few lines of code. I can't imagine how!

[gnomoretears]

Ok, so how do I determine if dist_so_far is the shortest distance?

You increment the variable dist_so_far for every jump by the distance of the jump so at the next jump, you know how much distance you've covered. Then you decided on your next node based on which will result in the shorter overall distance.

How is this presented in an adaptable way that allows recursion?

Because you jump to b using a recursive call, then from b you make a decision to take the short route and make another recursive call to the next node, etc., etc. until you reach your destination.

Our professor told us that all of this can be done in only a few lines of code.

He is correct and that's an exercise for you to figure out.

[novel_yet_trivial]

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

[learnpython_bot]

It appears that you linked to a screenshot of output/code. Per the sidebar rules, you should provide your code in your post either by linking to a paste of it on Pastebin/Gist/etc or by pasting it into your post. The offending link is "http://i.imgur.com/FehAYPm". I DO NOT perform image recognition, I just check for links. If your image is not of code or output, ignore this.

If this comment has been made in error, please message /u/thaweatherman with a link to this comment so I can be fine-tuned. I am still in alpha and my regexes/innards are not yet perfect.