Solving Dijkstra's algorithm - passing costs / parents with two edges

Question

I have a graph like this:

# graph table
graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['c'] = 4
graph['a']['d'] = 2 

graph['b'] = {}
graph['b']['a'] = 8
graph['b']['d'] = 7

graph['c'] = {}
graph['c']['d'] = 6
graph['c']['finish'] = 3

graph['d'] = {}
graph['d']['finish'] = 1
graph['finish'] = {}

And I am trying to find the fastest way from S to F.

In the first example in the book only one edge was connected to one node, in this example for example, node D has 3 weights and a cost table was used:

costs = {}
infinity = float('inf')
costs['a'] = 5
costs['b'] = 2
costs['c'] = 4 
costs['d'] = # there is 3 costs to node D, which one to select?
costs['finish'] = infinity

And a parents table:

parents = {}
parents['a'] = 'start' # why not start and b since both `S` and `B` can be `A` nodes parent?
parents['b'] = 'start'
parents['c'] = 'a'
parents['d'] =  # node D can have 3 parents
parents['finish'] = None

But this also works, by works I mean no error is thrown, so do I only have to name the parents from the first node S?

parents = {}
parents['a'] = 'start' 
parents['b'] = 'start'
parents['finish'] = None

The code:

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]

        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node



node = find_lowest_cost_node(costs)

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if costs[n] > new_cost:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)


def find_path(parents, finish):
  path = []
  node = finish
  while node:
      path.insert(0, node)
      if parents.__contains__(node):
          node = parents[node]
      else:
          node = None
  return path


path = find_path(parents, 'finish')
distance = costs['finish']

print(f'Path is: {path}')
print(f'Distance from start to finish is: {distance}')

I get:

Path is: ['finish']
Distance from start to finish is: inf

Where is my mistake and how should I add cost and parent to a node which can be visited from more than 1 node?

Edit I do believe this is not the best approach for this problem, the best in practice solution / recommendations are welcome.

user_8087999 · Answer

You do not need to initialise the cost table with more than costs['start'] = 0 or the parents dictionary with more than parents = {}. That is what your algorithm is going to create for you!

The only other change you need to make is to your while loop. It just needs to check whether the new node has already been detected before. If so then we check to see whether the new path is shorter and update as required; if not then we establish the new path.

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if n in costs:
          if costs[n] > new_cost:
              costs[n] = new_cost
              parents[n] = node
      else:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)

I think there are much neater ways to deal with graphs but this is the minimal change needed to make your code work as required. Hope it's helpful!

Solving Dijkstra's algorithm - passing costs / parents with two edges

1 Answers