LabEx
Log In Join For Free

Graph Shortest Path

AlgorithmAlgorithmBeginner
Practice Now

This tutorial is from open-source community. Access the source code

Introduction

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. It is a fundamental problem in network optimization and has applications in transportation, communication, and computer networking.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/FileHandlingGroup(["`File Handling`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python(("`Python`")) -.-> python/PythonStandardLibraryGroup(["`Python Standard Library`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") python/FileHandlingGroup -.-> python/with_statement("`Using with Statement`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/BasicConceptsGroup -.-> python/type_conversion("`Type Conversion`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ModulesandPackagesGroup -.-> python/importing_modules("`Importing Modules`") python/ModulesandPackagesGroup -.-> python/using_packages("`Using Packages`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/PythonStandardLibraryGroup -.-> python/data_collections("`Data Collections`") python/PythonStandardLibraryGroup -.-> python/os_system("`Operating System and System`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268830{{"`Graph Shortest Path`"}} algorithm/graphs_trees -.-> lab-268830{{"`Graph Shortest Path`"}} python/with_statement -.-> lab-268830{{"`Graph Shortest Path`"}} python/variables_data_types -.-> lab-268830{{"`Graph Shortest Path`"}} python/strings -.-> lab-268830{{"`Graph Shortest Path`"}} python/type_conversion -.-> lab-268830{{"`Graph Shortest Path`"}} python/conditional_statements -.-> lab-268830{{"`Graph Shortest Path`"}} python/for_loops -.-> lab-268830{{"`Graph Shortest Path`"}} python/while_loops -.-> lab-268830{{"`Graph Shortest Path`"}} python/lists -.-> lab-268830{{"`Graph Shortest Path`"}} python/tuples -.-> lab-268830{{"`Graph Shortest Path`"}} python/function_definition -.-> lab-268830{{"`Graph Shortest Path`"}} python/default_arguments -.-> lab-268830{{"`Graph Shortest Path`"}} python/importing_modules -.-> lab-268830{{"`Graph Shortest Path`"}} python/using_packages -.-> lab-268830{{"`Graph Shortest Path`"}} python/standard_libraries -.-> lab-268830{{"`Graph Shortest Path`"}} python/classes_objects -.-> lab-268830{{"`Graph Shortest Path`"}} python/constructor -.-> lab-268830{{"`Graph Shortest Path`"}} python/polymorphism -.-> lab-268830{{"`Graph Shortest Path`"}} python/encapsulation -.-> lab-268830{{"`Graph Shortest Path`"}} python/raising_exceptions -.-> lab-268830{{"`Graph Shortest Path`"}} python/data_collections -.-> lab-268830{{"`Graph Shortest Path`"}} python/os_system -.-> lab-268830{{"`Graph Shortest Path`"}} python/build_in_functions -.-> lab-268830{{"`Graph Shortest Path`"}} end

Graph Shortest Path

Problem

Given a directed graph with weighted edges, find the shortest path between two nodes.

Requirements

To solve this problem, we need to consider the following requirements:

  • Is this a directional graph? - Yes
  • Could the graph have cycles? - Yes
    • Note: If the answer were no, this would be a DAG.
  • Are the edges weighted? - Yes
    • Note: If the edges were not weighted, we could do a BFS
  • Are the edges all non-negative numbers? - Yes
    • Note: Graphs with negative edges can be done with Bellman-Ford
      • Graphs with negative cost cycles do not have a defined shortest path
  • Do we have to check for non-negative edges? - No
  • Can we assume this is a connected graph? - Yes
  • Can we assume the inputs are valid? - No
  • Can we assume we already have a graph class? - Yes
  • Can we assume we already have a priority queue class? - Yes
  • Can we assume this fits memory? - Yes

Example

Consider the following graph:

graph.add_edge('a', 'b', weight=5)
graph.add_edge('a', 'c', weight=3)
graph.add_edge('a', 'e', weight=2)
graph.add_edge('b', 'd', weight=2)
graph.add_edge('c', 'b', weight=1)
graph.add_edge('c', 'd', weight=1)
graph.add_edge('d', 'a', weight=1)
graph.add_edge('d', 'g', weight=2)
graph.add_edge('d', 'h', weight=1)
graph.add_edge('e', 'a', weight=1)
graph.add_edge('e', 'h', weight=4)
graph.add_edge('e', 'i', weight=7)
graph.add_edge('f', 'b', weight=3)
graph.add_edge('f', 'g', weight=1)
graph.add_edge('g', 'c', weight=3)
graph.add_edge('g', 'i', weight=2)
graph.add_edge('h', 'c', weight=2)
graph.add_edge('h', 'f', weight=2)
graph.add_edge('h', 'g', weight=2)

We can find the shortest path between node 'a' and node 'i' using the ShortestPath class:

shortest_path = ShortestPath(graph)
result = shortest_path.find_shortest_path('a', 'i')

The expected result is:

['a', 'c', 'd', 'g', 'i']

We can also check the weight of the shortest path:

self.assertEqual(shortest_path.path_weight['i'], 8)

Summary

The shortest path problem is a fundamental problem in network optimization. To solve this problem, we need to consider the requirements of the graph, such as whether it is directional, whether it has cycles, and whether the edges are weighted. We can use the ShortestPath class to find the shortest path between two nodes in a graph.

Other Algorithm Tutorials you may like

Related Algorithm Courses
Quick Start with Algorithm

Quick Start with Algorithm

AlgorithmPython
Beginner
Implementing Queue Data Structure in C

Implementing Queue Data Structure in C

CAlgorithm
Beginner

We use cookies for a number of reasons, such as keeping the website reliable and secure, to improve your experience on our website and to see how you interact with it. By accepting, you agree to our use of such cookies. Privacy Policy