Python DFS Shortest Path Search with weighted, undirected graph

2
votes

I'm having trouble parsing through this graph dictionary: 

routes = {'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)]}

How do I separate out the values of each edge while running the dictionary through a DFS Search looking at 2 keys? I'm not very familiar with dict.

So far I have, 

def dfs(graph, start, end, path):
    path = path + [start]
    if start == end: 
        paths.append(path)
    for node in graph.childrenOf(start):
        if node not in path:
            dfs(graph, node, end, path)

I need to return the smallest weighted path, so I need the numbers in the values separated out and summed as the program runs.

2
pythonrecursiondictionarygraph-theorydepth-first-search
What part exactly of the dictionary you want? Keys, values or part of the values (which parts)? - nbro
Keys are the colon left side stuff and the right side stuff are, you guessed, the values - nbro
I need to return the smallest weighted path, so I need the numbers in the values separated out and summed as the program runs. - N.B.48
defaultdict(dict) is convenient. If you need something faster, there are other data structures which may be slightly less convenient but much faster. - Brian Cain

2 Answers

1
votes

You can build your graph using a dict of dicts:

routes = {'a': {'b': 5.0, 'c': 8.0}, 'c': {'a': 8.0, 'd': 2.0}}

Then routes['a']['b'] will return the weight, which is 5.0 in this case. If you need to get all the children of a node you can do routes['a'].keys() and that will return ['c', 'b'].

0
votes

routes is your graph, in adjacency-list format. Each key is a node, the value being a list of (other_node, edge_weight) tuples. So what you're looking for is how "graph.childrenOf" should work.

Assuming start, end are simple string node names (like 'a') you can just look them up in the dictionary; e.g. graph[a] will give you [('b', 5.0), ('c', 8.0)]. You can iterate directly over both the node and weight using python's nifty built-in tuple unpacking, like so:

# replace your for loop with this:
for node, weight in graph[start]: