Algorithms on Graphs

Save on skills that make you shine with 40% off 3 months of Coursera Plus. Save now

Algorithms on Graphs

This course is part of Data Structures and Algorithms Specialization

Instructors: Neil Rhodes

126,045 already enrolled

Included with

Learn more

5 modules

Gain insight into a topic and learn the fundamentals.

2,272 reviews

Intermediate level

Some related experience required

Flexible schedule

2 weeks at 10 hours a week

Learn at your own pace

90%

Most learners liked this course

5 modules

Gain insight into a topic and learn the fundamentals.

2,272 reviews

Intermediate level

Some related experience required

Flexible schedule

2 weeks at 10 hours a week

Learn at your own pace

90%

Most learners liked this course

Skills you'll gain

Details to know

Shareable certificate

Add to your LinkedIn profile

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the Data Structures and Algorithms Specialization

When you enroll in this course, you'll also be enrolled in this Specialization.

Learn new concepts from industry experts
Gain a foundational understanding of a subject or tool
Develop job-relevant skills with hands-on projects
Earn a shareable career certificate

There are 5 modules in this course

If you have ever used a navigation service to find optimal route and estimate time to destination, you've used algorithms on graphs. Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect a set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs.

In this online course, you will first learn what a graph is and what are some of the most important properties. Then you'll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will then talk about shortest paths algorithms — from the basic ones to those which open door for 1000000 times faster algorithms used in Google Maps and other navigational services. You will use these algorithms if you choose to work on our Fast Shortest Routes industrial capstone project. We will finish with minimum spanning trees which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.

Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders hot in Facebook, you're going to work with graphs and algorithms on graphs. In this module, you will learn ways to represent a graph as well as basic algorithms for decomposing graphs into parts. In the programming assignment of this module, you will apply the algorithms that you’ve learned to implement efficient programs for exploring mazes, analyzing Computer Science curriculum, and analyzing road networks. In the first week of the module, we focus on undirected graphs.

What's included

5 videos3 readings1 programming assignment

5 videosTotal 43 minutes

Graph Basics5 minutes
Representing Graphs10 minutes
Exploring Graphs15 minutes
Connectivity6 minutes
Previsit and Postvisit Orderings8 minutes

3 readingsTotal 30 minutes

Welcome10 minutes
Slides and External References10 minutes
Slides and External References10 minutes

1 programming assignmentTotal 180 minutes

Programming Assignment 1: Decomposition of Graphs180 minutes

This week we continue to study graph decomposition algorithms, but now for directed graphs.

What's included

4 videos1 reading1 programming assignment

In this module you will study algorithms for finding Shortest Paths in Graphs. These algorithms have lots of applications. When you launch a navigation app on your smartphone like Google Maps or Yandex.Navi, it uses these algorithms to find you the fastest route from work to home, from home to school, etc. When you search for airplane tickets, these algorithms are used to find a route with the minimum number of plane changes. Unexpectedly, these algorithms can also be used to determine the optimal way to do currency exchange, sometimes allowing to earh huge profit! We will cover all these applications, and you will learn Breadth-First Search, Dijkstra's Algorithm and Bellman-Ford Algorithm. These algorithms are efficient and lay the foundation for even more efficient algorithms which you will learn and implement in the Shortest Paths Capstone Project to find best routes on real maps of cities and countries, find distances between people in Social Networks. In the end you will be able to find Shortest Paths efficiently in any Graph. This week we will study Breadth-First Search algorithm.

What's included

8 videos1 reading1 programming assignment

8 videosTotal 56 minutes

Applications3 minutes
Paths and Distances9 minutes
Breadth-First Search7 minutes
Breadth-First Search (continued)8 minutes
Implementation and Analysis5 minutes
BFS Properties10 minutes
Correct Distances4 minutes
Shortest Path Tree11 minutes

1 readingTotal 10 minutes

Slides and External References10 minutes

1 programming assignmentTotal 180 minutes

Programming Assignment 3: Paths in Graphs180 minutes

This week we continue to study Shortest Paths in Graphs. You will learn Dijkstra's Algorithm which can be applied to find the shortest route home from work. You will also learn Bellman-Ford's algorithm which can unexpectedly be applied to choose the optimal way of exchanging currencies. By the end you will be able to find shortest paths efficiently in any Graph.

What's included

13 videos2 readings1 programming assignment

13 videosTotal 90 minutes

Fastest Route8 minutes
Naive Algorithm9 minutes
Dijkstra's Algorithm5 minutes
Dijkstra Example5 minutes
Implementation6 minutes
Proof of Correctness7 minutes
Analysis5 minutes
Currency Exchange6 minutes
Reduction to Shortest Paths10 minutes
Bellman-Ford Algorithm6 minutes
Proof of Correctness6 minutes
Negative Cycles7 minutes
Infinite Arbitrage9 minutes

2 readingsTotal 20 minutes

Slides and External References10 minutes
Slides and External References10 minutes

1 programming assignmentTotal 180 minutes

Programming Assignment 4: Paths in Graphs180 minutes

In this module, we study the minimum spanning tree problem. We will cover two elegant greedy algorithms for this problem: the first one is due to Kruskal and uses the disjoint sets data structure, the second one is due to Prim and uses the priority queue data structure. In the programming assignment for this module you will be computing an optimal way of building roads between cities and an optimal way of partitioning a given set of objects into clusters (a fundamental problem in data mining).

What's included

5 videos1 reading1 programming assignment

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Instructors

Instructor ratings

(178 ratings)

Neil Rhodes

University of California San Diego

7 Courses757,070 learners

Daniel M Kane

University of California San Diego

5 Courses739,099 learners

Offered by

University of California San Diego

Explore more from Algorithms

Status: Free Trial
Packt
Intermediate Algorithms: Graphs, Trees, and Backtracking
Course
Status: Free Trial
University of California San Diego
Introduction to Graph Theory
Course
Pragmatic AI Labs
Graph Algorithms with Rust
Course
28DIGITAL
Approximation Algorithms
Course

Why people choose Coursera for their career

Felipe M.

Learner since 2018

"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."

Jennifer J.

Learner since 2020

"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."

Larry W.

Learner since 2021

"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."

Chaitanya A.

"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

5 stars
79.41%
4 stars
16.62%
3 stars
2.59%
2 stars
0.79%
1 star
0.57%

Showing 3 of 2272

Reviewed on Feb 27, 2017

Fairly good course. I wish the edge cases for some of the programming assignments had some more discussions. Needed some sifting through the forums while stuck.

Reviewed on Jan 6, 2021

I've wanted to learn about Graphs and the algorithms associated with it for a long time, and I cannot imagine a better course to learn it from. Thank you?

Reviewed on Oct 11, 2020

It was a great course with great illustration, but the best part of it was the proof of correctness with detailed steps of time complexity computations!

View more reviews

Frequently asked questions

To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.