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.
Algorithms on Graphs
Algorithms on Graphs
This course is part of Data Structures and Algorithms Specialization
Instructors: Neil Rhodes
120,879 already enrolled
Included with 
Gain insight into a topic and learn the fundamentals.
4.7
(2,268 reviews)
Intermediate level
Some related experience required
Flexible schedule
Approx. 54 hours
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
Assessments
1 assignment
Taught in English
See how employees at top companies are mastering in-demand skills
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
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV
Share it on social media and in your performance review
There are 6 modules in this course
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
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
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
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
In this module, you will learn Advanced Shortest Paths algorithms that work in practice 1000s (up to 25000) of times faster than the classical Dijkstra's algorithm on real-world road networks and social networks graphs. You will work on a Programming Project based on these algorithms. You will find the shortest paths on the real maps of parts of US and the shortest paths connecting people in the social networks. We encourage you not only to use the ideas from this module's lectures in your implementations, but also to come up with your own ideas for speeding up the algorithm! We encourage you to compete on the forums to see whose implementation is the fastest one :)
What's included
17 videos3 readings1 assignment1 programming assignment
Instructors
Instructor ratings
4.5 (176 ratings)Offered by
Recommended if you're interested in Algorithms
University of California San Diego
Princeton University
EIT Digital
University of California San Diego
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
4.7
2,268 reviews
- 5 stars
79.41%
- 4 stars
16.61%
- 3 stars
2.60%
- 2 stars
0.79%
- 1 star
0.57%
Showing 3 of 2268
NG
5
Reviewed on Jun 27, 2019
Loved the explanations and proofs. They are so explicitly told. And the discussion forum for you well assorted problems in assignment is really helpful.
AF
5
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!
CS
5
Reviewed on Jun 30, 2019
Excellent Course for anyone looking to expertise Graph Algorithm. Professor's explained each problem and algorithm in a very easy to learn approach. Grades are tough and yet func to get challenged.
New to Algorithms? Start here.
Open new doors with Coursera Plus
Unlimited access to 10,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription
Advance your career with an online degree
Earn a degree from world-class universities - 100% online
Join over 3,400 global companies that choose Coursera for Business
Upskill your employees to excel in the digital economy
Frequently asked questions
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
The course may not offer an audit option. 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. If you only want to read and view the course content, you can audit the course for free.
If you subscribed, you get a 7-day free trial during which you can cancel at no penalty. After that, we don’t give refunds, but you can cancel your subscription at any time. See our full refund policy.
More questions
Financial aid available,