How do I calculate the length of a path from a weighted graph in Python?

Question

I am doing this project and I'm having a problem with finding out which path has the shortest length. The setup is a supermarket. You start at the entrance and you get out at the cash deck. The points A,B,C,D are the points in the sections in the supermarket like the bake-off etc. At the input 'via' you can give the points which you want to pass.

#e = entrance
#k = cash desk
graph1 = {'e':{'a':1, 'b':5, 'c':6, 'd':6},
    'a':{'e':2, 'b':4, 'c':5, 'd':5, 'k':7},
    'b':{'e':5, 'a':5, 'c':3, 'd':5, 'k':6},
    'c':{'e':6, 'a':5, 'b':3, 'd':4, 'k':5},
    'd':{'e':6, 'a':3, 'b':5, 'c':4, 'k':2},
    'k':{'a':7, 'b':6, 'c':5, 'd':2}
}

start = input('start')
end = input('end')
required = input('via').split(',')

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

def exists_in_graph(graph, nodes):
  for node in nodes:
    if not node in graph:
      return False
  return True

allPaths = find_all_paths(graph1, start, end)
allPathsTroughNodes = list(filter(lambda x: exists_in_graph(x, required), 
allPaths))
print(allPathsTroughNodes)

The output:

start e
end k
via a,c,d
[['e', 'a', 'b', 'c', 'd', 'k'], ['e', 'a', 'b', 'd', 'c', 'k'], ['e', 'a', 
'c', 'b', 'd', 'k'], ['e', 'a', 'c', 'd', 'b', 'k'], ['e', 'a', 'c', 'd', 
'k'], ['e', 'a', 'd', 'b', 'c', 'k'], ['e', 'a', 'd', 'c', 'b', 'k'], ['e', 
'a', 'd', 'c', 'k'], ['e', 'b', 'a', 'c', 'd', 'k'], ['e', 'b', 'a', 'd', 
'c', 'k'], ['e', 'b', 'c', 'a', 'd', 'k'], ['e', 'b', 'c', 'd', 'a', 'k'], 
['e', 'b', 'd', 'a', 'c', 'k'], ['e', 'b', 'd', 'c', 'a', 'k'], ['e', 'c', 
'a', 'b', 'd', 'k'], ['e', 'c', 'a', 'd', 'b', 'k'], ['e', 'c', 'a', 'd', 
'k'], ['e', 'c', 'b', 'a', 'd', 'k'], ['e', 'c', 'b', 'd', 'a', 'k'], ['e', 
'c', 'd', 'a', 'b', 'k'], ['e', 'c', 'd', 'a', 'k'], ['e', 'c', 'd', 'b', 
'a', 'k'], ['e', 'd', 'a', 'b', 'c', 'k'], ['e', 'd', 'a', 'c', 'b', 'k'], 
['e', 'd', 'a', 'c', 'k'], ['e', 'd', 'b', 'a', 'c', 'k'], ['e', 'd', 'b', 
'c', 'a', 'k'], ['e', 'd', 'c', 'a', 'b', 'k'], ['e', 'd', 'c', 'a', 'k'], 
['e', 'd', 'c', 'b', 'a', 'k']]

But I have no clue how I can calculate the length of each found path and how I can get the shortest one out of these.

score 1 · Answer 1 · answered Dec 28 '17 at 12:03

You need to accumulate the path lengths while you're building the paths. It's possible to modify your existing code to do that, but it gets messy. A cleaner way to do this is to convert your function into a generator so that it yields paths as it finds them, rather than storing them in a list of paths.

We can pass the generator output to the sorted function to get a list of paths sorted by their length.

import sys

graph1 = {
    'e': {'a': 1, 'b': 5, 'c': 6, 'd': 6},
    'a': {'e': 2, 'b': 4, 'c': 5, 'd': 5, 'k': 7},
    'b': {'e': 5, 'a': 5, 'c': 3, 'd': 5, 'k': 6},
    'c': {'e': 6, 'a': 5, 'b': 3, 'd': 4, 'k': 5},
    'd': {'e': 6, 'a': 3, 'b': 5, 'c': 4, 'k': 2},
    'k': {'a': 7, 'b': 6, 'c': 5, 'd': 2}
}

#start = input('start ')
#end = input('end ')
#required = input('via ').split(',')
#if required == ['']:
    #required = []

# Hard-code some input data to make it easier to test the code
start, end = 'e', 'k'
required = []

def find_all_paths(graph, start, end, path=None, pathlen=0):
    if path is None:
        path = []
    path = path + [start]
    if start == end:
        yield pathlen, path
    if not start in graph:
        yield [], 0
        return

    for node, val in graph[start].items():
        if node not in path:
            yield from find_all_paths(graph, node, end, path, pathlen + val)

def exists_in_graph(graph, nodes):
    for node in nodes:
        if not node in graph:
            return False
    return True

if not exists_in_graph(graph1, [start, end] + required):
    print('Bad data!')
    sys.exit()

all_paths = sorted(find_all_paths(graph1, start, end))
for pathlen, path in all_paths:
    if exists_in_graph(path, required):
        print(path, pathlen)

output

['e', 'a', 'd', 'k'] 8
['e', 'a', 'k'] 8
['e', 'd', 'k'] 8
['e', 'a', 'b', 'k'] 11
['e', 'a', 'c', 'k'] 11
['e', 'b', 'k'] 11
['e', 'c', 'k'] 11
['e', 'a', 'b', 'd', 'k'] 12
['e', 'a', 'c', 'd', 'k'] 12
['e', 'b', 'd', 'k'] 12
['e', 'c', 'd', 'k'] 12
['e', 'a', 'b', 'c', 'k'] 13
['e', 'b', 'c', 'k'] 13
['e', 'a', 'b', 'c', 'd', 'k'] 14
['e', 'b', 'c', 'd', 'k'] 14
['e', 'a', 'c', 'b', 'k'] 15
['e', 'a', 'd', 'c', 'k'] 15
['e', 'c', 'b', 'k'] 15
['e', 'd', 'c', 'k'] 15
['e', 'a', 'c', 'b', 'd', 'k'] 16
['e', 'c', 'b', 'd', 'k'] 16
['e', 'd', 'a', 'k'] 16
['e', 'a', 'd', 'b', 'k'] 17
['e', 'b', 'a', 'd', 'k'] 17
['e', 'b', 'a', 'k'] 17
['e', 'd', 'b', 'k'] 17
['e', 'c', 'a', 'd', 'k'] 18
['e', 'c', 'a', 'k'] 18
['e', 'a', 'b', 'd', 'c', 'k'] 19
['e', 'a', 'd', 'b', 'c', 'k'] 19
['e', 'a', 'd', 'c', 'b', 'k'] 19
['e', 'b', 'd', 'c', 'k'] 19
['e', 'd', 'a', 'b', 'k'] 19
['e', 'd', 'a', 'c', 'k'] 19
['e', 'd', 'b', 'c', 'k'] 19
['e', 'd', 'c', 'b', 'k'] 19
['e', 'b', 'a', 'c', 'k'] 20
['e', 'b', 'c', 'a', 'd', 'k'] 20
['e', 'b', 'c', 'a', 'k'] 20
['e', 'b', 'd', 'a', 'k'] 20
['e', 'c', 'd', 'a', 'k'] 20
['e', 'a', 'c', 'd', 'b', 'k'] 21
['e', 'b', 'a', 'c', 'd', 'k'] 21
['e', 'c', 'a', 'b', 'k'] 21
['e', 'c', 'b', 'a', 'd', 'k'] 21
['e', 'c', 'b', 'a', 'k'] 21
['e', 'c', 'd', 'b', 'k'] 21
['e', 'd', 'a', 'b', 'c', 'k'] 21
['e', 'b', 'c', 'd', 'a', 'k'] 22
['e', 'c', 'a', 'b', 'd', 'k'] 22
['e', 'd', 'c', 'a', 'k'] 22
['e', 'b', 'd', 'a', 'c', 'k'] 23
['e', 'c', 'd', 'a', 'b', 'k'] 23
['e', 'd', 'a', 'c', 'b', 'k'] 23
['e', 'd', 'b', 'a', 'k'] 23
['e', 'b', 'a', 'd', 'c', 'k'] 24
['e', 'c', 'b', 'd', 'a', 'k'] 24
['e', 'd', 'c', 'a', 'b', 'k'] 25
['e', 'd', 'c', 'b', 'a', 'k'] 25
['e', 'b', 'd', 'c', 'a', 'k'] 26
['e', 'd', 'b', 'a', 'c', 'k'] 26
['e', 'd', 'b', 'c', 'a', 'k'] 26
['e', 'c', 'a', 'd', 'b', 'k'] 27
['e', 'c', 'd', 'b', 'a', 'k'] 27

Another way to call the find_all_paths generator is

valid_paths = sorted((pathlen, path)
    for pathlen, path in find_all_paths(graph1, start, end)
        if exists_in_graph(path, required)
)
for pathlen, path in valid_paths:
    print(path, pathlen)

That way we can filter the unwanted paths before they get sorted. And if you just want the shortest path you can replace the call to sorted with min.

pathlen, path = min((pathlen, path)
    for pathlen, path in find_all_paths(graph1, start, end)
        if exists_in_graph(path, required)
)
print(path, pathlen)

output

['e', 'a', 'd', 'k'] 8

I've made a couple of other small changes to your code.

If the user enters nothing at the 'via' prompt then required is set to a list containing the empty string, and that will mess up your exists_in_graph test, so if that happens we set required to the empty list.

In your version of find_all_paths you give path a default value of the empty list. That will mess things up if you want to call find_all_paths more than once, because default args are evaluated when the function is created, not when it's called. So if you call find_all_paths again without supplying a path arg it will continue using the same default path list that it originally used, it won't use a new empty list. The usual way to deal with this is to use a default of None, as I've done in my code. For more info on this important topic, please see “Least Astonishment” and the Mutable Default Argument.

How do I calculate the length of a path from a weighted graph in Python?

1 Answers1