Graph Data Structures: Implementing Graph Traversal & Shortest Path Algorithms

Python    |    Intermediate
  • 11 videos | 1h 29m 48s
  • Includes Assessment
  • Earns a Badge
Rating 4.6 of 16 users Rating 4.6 of 16 users (16)
What makes the graph data structure very interesting and powerful is the large number of algorithms that can be run on graphs to extract insights. Common graph algorithms include traversing a graph and computing the shortest path between nodes. Implementing these algorithms is a great way to learn how graphs are explored and optimized. In this course, learn how graphs can be traversed by studying both depth-first and breadth-first graph traversal and discover how they can be implemented using a stack and a queue respectively. Next, explore how to compute the shortest path in an unweighted graph. And finally, use Dijkstra's algorithm to compute the shortest path in a weighted graph. Upon completion of this course, you will be able to implement optimal algorithms on graphs.

WHAT YOU WILL LEARN

  • Discover the key concepts covered in this course
    Recall how depth-first and breadth-first traversal works
    Implement breadth-first traversal using a queue data structure
    Implement depth-first traversal using a stack, as well as using recursion
    Compute the shortest path in an unweighted graph using breadth-first traversal and the distance table
    Implement the shortest path algorithm for an unweighted graph
  • Recall the properties of greedy algorithms
    List the relaxation techniques used to populate the distance table in dijkstra's algorithm
    Compute the shortest path in a weighted graph using greedy traversal and the distance table
    Implement dijkstra's algorithm to compute the shortest path in a weighted graph
    Summarize the key concepts covered in this course

IN THIS COURSE

  • 2m 15s
  • 8m 27s
    Upon completion of this video, you will be able to recall how depth-first and breadth-first traversal work. FREE ACCESS
  • Locked
    3.  Implementing Breadth-first Traversal
    9m 5s
    Find out how to implement breadth-first traversal using a queue data structure. FREE ACCESS
  • Locked
    4.  Implementing Depth-first Traversal
    9m 55s
    In this video, you will learn how to implement depth-first traversal using a stack, as well as using recursion. FREE ACCESS
  • Locked
    5.  Shortest Path Algorithm
    12m 46s
    Learn how to compute the shortest path in an unweighted graph using breadth-first traversal and a distance table. FREE ACCESS
  • Locked
    6.  Implementing the Shortest Path Algorithm
    13m 22s
    In this video, you will learn how to implement the shortest path algorithm for an unweighted graph. FREE ACCESS
  • Locked
    7.  Greedy Algorithms
    8m 36s
    After completing this video, you will be able to recall the properties of greedy algorithms. FREE ACCESS
  • Locked
    8.  Graph Relaxation Techniques
    3m 9s
    After completing this video, you will be able to list the relaxation techniques used to populate the distance table in Dijkstra's algorithm. FREE ACCESS
  • Locked
    9.  Dijkstra's Algorithm
    7m 19s
    During this video, you will learn how to compute the shortest path in a weighted graph using greedy traversal and the distance table. FREE ACCESS
  • Locked
    10.  Implementing Dijkstra's Algorithm
    12m 55s
    In this video, you will implement Dijkstra's algorithm to compute the shortest path in a weighted graph. FREE ACCESS
  • Locked
    11.  Course Summary
    1m 58s

EARN A DIGITAL BADGE WHEN YOU COMPLETE THIS COURSE

Skillsoft is providing you the opportunity to earn a digital badge upon successful completion on some of our courses, which can be shared on any social network or business platform.

Digital badges are yours to keep, forever.

YOU MIGHT ALSO LIKE

Journey The Essential Data Structures and Algorithms in Python
Book Data Structures with Python: Get Familiar with the Common Data Structures and Algorithms in Python
Course Math & Optimizations: Introducing Sets & Set Operations
Rating 4.4 of 177 users Rating 4.4 of 177 users (177)

PEOPLE WHO VIEWED THIS ALSO VIEWED THESE

Course Data Structures & Algorithms in Python: Sorting Algorithms
Rating 4.5 of 183 users Rating 4.5 of 183 users (183)
Course Data Structures & Algorithms in Java: Introduction
Rating 4.5 of 100 users Rating 4.5 of 100 users (100)
Course Control Structures in C: Looping & Unconditional Control Structures
Rating 4.3 of 51 users Rating 4.3 of 51 users (51)