How to perform depth first search in graph represented as dictionary

Question

Here is the graph represented as dictionary with me :

{'A': {'C': 4, 'B': 5}, 
   'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6}, 
   'B': {'A': 5, 'C': 2, 'D': 3}, 
   'E': {'F': 1}, 
   'D': {'C': 10, 'B': 3}, 
   'F': {'C': 6, 'E': 1}}

I need to perform DFS from one node to other and get all the weights along the edges. Also from one node to other there can only be a single path. I am new to python and need help.

Answer 1

The original code snippet is taken from this great article. This implementation uses generator to get paths with DFS. I updated it a bit to get weights values for each path.

graph = {
    'A': {'C': 4, 'B': 5},
    'C': {'A': 4, 'B': 2, 'D': 10, 'F': 6},
    'B': {'A': 5, 'C': 2, 'D': 3},
    'E': {'F': 1},
    'D': {'C': 10, 'B': 3},
    'F': {'C': 6, 'E': 1}
}

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

def get_weights(graph, path):
    value = 0
    node = graph[path[0]]
    for item in path[1:]:
        value += node[item]
        node = graph[item]
    return value

for path in dfs_paths(graph, 'A', 'F'):
    print(path, get_weights(graph, path))

### ['A', 'B', 'D', 'C', 'F'] 24
### ['A', 'B', 'C', 'F'] 13
### ['A', 'C', 'F'] 10