avatar Bite 273. Shortest path (Graph Bite)

Graph theory is popular in Math and Computer Science. A graph is a set of V of vertices and a set of E of Edges, such that each edge in E connected two of the vertices in V.

Vertices and edges can be labeled or unlabelled. When they are labeled, the number can be viewed as weight or distance depends on the context.

It has a wide array of applications from social networking to neural network to engineering field. Today we are going to tackle one of the interesting and challenging graph bites.

Given a dictionary of dictionaries that represent a major airline hub and its connecting cities and corresponding distance.

Please find out the shortest path from city A to city B. You can assume there is always a route between these two cities. Example:

hub = { 
          'a': {'b': 2, 'c': 4, 'e': 1},
          'b': {'a': 2, 'd': 3},
          'c': {'a': 4, 'd': 6},
          'd': {'c': 6, 'b': 3, 'e': 2},
          'e': {'a': 1, 'd': 2},
>>> shortest_path(hub, 'a', 'd')
Expected result: cost and path:
  (3, ['a', 'e', 'd'])

Login and get coding
go back Advanced level
Bitecoin 4X

46 out of 49 users completed this Bite.
Will you be Pythonista #47 to crack this Bite?
Resolution time: ~81 min. (avg. submissions of 5-240 min.)
Pythonistas rate this Bite 8.0 on a 1-10 difficulty scale.
» Up for a challenge? 💪

We use Python 3.8