How to find total cost of each path in graph using dictionary in python-CodePudding

My task is to find total cost associated with each path and then tell the shortest cost path. In the given graph dict I had to assign random cost to each node and then when finding all the paths i also have to find the total cost associated with that path print the cost along with the path and then print the shortest cost path.

Problem is that I can print all the paths but I am unable to find the total cost associated with that path.

My code is

enter code hgraph = {'A': {'B':2, 'C':3},
     'B': {'C':2, 'D':5},
     'C': {'D':4, 'G':2},
     'D': {'C':6, 'E':4},
     'E': {'F':1},
     'F': [],
     'G': []}


def find_all_paths(graph, start, end, path=[]):
    path = path   [start]
    if start == end:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            paths  = find_all_paths(graph, node, end, path)

    return paths

print("Path : ",find_all_paths(graph, 'A', 'F'))

I tried using this but it return cost of that node only and I its impossible to integrate it in the loop

cost= cost   (str(graph['A'].get('B') (graph['A'].get('C'))))

CodePudding user response：

Since Python 3.10 you can write it for a given path like:

from itertools import pairwise

cost = sum(graph[f][t] for f, t in pairwise(path))

See the docs how to replace pairwise before 3.10.

CodePudding user response：

def path_cost(path):
    cost = 0
    for i in range(len(path)-1):
        if len(graph[path[i]]) != 0:
            cost  = graph[path[i]][path[i 1]]
    return cost