Graph Theory | Shortest Path | Unweighted Graph

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. The problem of finding the shortest path between two nodes in an unweighted graph can be solved using a breadth-first search algorithm.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) 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/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/graphs_trees("`Graphs Trees`") 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/DataStructuresGroup -.-> python/dictionaries("`Dictionaries`") 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/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} algorithm/graphs_trees -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/variables_data_types -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/strings -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/type_conversion -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/conditional_statements -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/for_loops -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/while_loops -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/lists -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/tuples -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/dictionaries -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/function_definition -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/default_arguments -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/importing_modules -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/using_packages -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/standard_libraries -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/classes_objects -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/constructor -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/polymorphism -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/encapsulation -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/raising_exceptions -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} python/build_in_functions -.-> lab-268829{{"`Graph Shortest Path Unweighted`"}} end

Graph Shortest Path Unweighted

Problem

Given a directed graph with no edge weights, find the shortest path between two nodes.

Requirements

To solve this problem, the following requirements must be met:

The graph is directed.
The graph is unweighted.
Graph and Node classes are already available.
The inputs are two nodes.
The output is a list of node keys that make up the shortest path.
If there is no path, return None.
The graph is connected.
The inputs are valid.
The algorithm must fit memory.

Example Usage

Suppose we have the following graph:

graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(0, 5)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 1)
graph.add_edge(3, 2)
graph.add_edge(3, 4)

We can find the shortest path between two nodes using the search_path function:

search_path(start=0, end=2) -> [0, 1, 3, 2]
search_path(start=0, end=0) -> [0]
search_path(start=4, end=5) -> None

Summary

In summary, the problem of finding the shortest path between two nodes in an unweighted graph can be solved using a breadth-first search algorithm. The algorithm must meet the requirements mentioned above to ensure its correctness and efficiency.

Graph Shortest Path Unweighted

Introduction

Skills Graph

Graph Shortest Path Unweighted

Problem

Requirements

Example Usage

Summary

Other Algorithm Tutorials you may like