Graph Data Structures: Implementing Graph Traversal & Shortest Path Algorithms
Python 3.7
| Intermediate
- 11 Videos | 1h 29m 48s
- Includes Assessment
- Earns a Badge
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 courserecall how depth-first and breadth-first traversal worksimplement breadth-first traversal using a queue data structureimplement depth-first traversal using a stack, as well as using recursioncompute the shortest path in an unweighted graph using breadth-first traversal and the distance tableimplement the shortest path algorithm for an unweighted graph
-
recall the properties of greedy algorithmslist the relaxation techniques used to populate the distance table in Dijkstra's algorithmcompute the shortest path in a weighted graph using greedy traversal and the distance tableimplement Dijkstra's algorithm to compute the shortest path in a weighted graphsummarize the key concepts covered in this course
IN THIS COURSE
-
1.Course Overview2m 15sUP NEXT
-
2.Depth-first and Breadth-first Traversal8m 27s
-
3.Implementing Breadth-first Traversal9m 5s
-
4.Implementing Depth-first Traversal9m 55s
-
5.Shortest Path Algorithm12m 46s
-
6.Implementing the Shortest Path Algorithm13m 22s
-
7.Greedy Algorithms8m 36s
-
8.Graph Relaxation Techniques3m 9s
-
9.Dijkstra's Algorithm7m 19s
-
10.Implementing Dijkstra's Algorithm12m 55s
-
11.Course Summary1m 58s
EARN A DIGITAL BADGE WHEN YOU COMPLETE THIS COURSE
Skillsoft is providing you the opportunity to earn a digital badge upon successful completion of this course, which can be shared on any social network or business platform
Digital badges are yours to keep, forever.