Algorithms on Graphs

Brought by: Coursera

Overview

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.

Syllabus

  • Decomposition of Graphs 1
    • 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.
  • Decomposition of Graphs 2
    • This week we continue to study graph decomposition algorithms, but now for directed graphs.
  • Paths in Graphs 1
    • 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.
  • Paths in Graphs 2
    • 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.
  • Minimum Spanning Trees
    • 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).
  • Advanced Shortest Paths Project (Optional)
    • 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 :)

Taught by

Alexander S. Kulikov and Michael Levin

Algorithms on Graphs
Go to course

Algorithms on Graphs

Brought by: Coursera

  • Coursera
  • Free
  • English
  • Certificate Available
  • Available at any time
  • intermediate
  • Arabic, French, Portuguese, Italian, German, Russian, English, Spanish, Thai, Indonesian, Kazakh, Hindi, Swedish, Korean, Greek, Chinese, Ukrainian, Japanese, Polish, Dutch, Turkish
8.1.2PHP Version271msRequest Duration2MBMemory UsageGET en/courses/{slug}Route
    • Booting (167ms)
    • Application (103ms)
    • 1 x Booting (61.7%)
      167.49ms
      1 x Application (38.05%)
      103.27ms
      14 templates were rendered
      • public.courses.show (resources/views/public/courses/show.blade.php)3bladefile
        Params
        0
        course
        1
        links
        2
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.courses.partials.details (resources/views/public/courses/partials/details.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.layouts.main (resources/views/public/layouts/main.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.meta (resources/views/public/layouts/partials/meta.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.navbar (resources/views/public/layouts/partials/navbar.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.links (resources/views/public/auth/profile/partials/links.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.layouts.partials.flash-session (resources/views/public/layouts/partials/flash-session.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      uri
      GET en/courses/{slug}
      middleware
      web, localize:en
      controller
      App\Http\Controllers\CourseController@show
      as
      en.courses.show
      namespace
      prefix
      /en
      where
      file
      app/Http/Controllers/CourseController.php:17-35
      7 statements were executed4.09ms
      • select * from `courses` where `slug_en` = 'algorithms-on-graphs' limit 1
        2.43ms/app/Http/Controllers/CourseController.php:20corspedia
        Metadata
        Bindings
        • 0. algorithms-on-graphs
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:20
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • update `courses` set `visitors` = `visitors` + 1, `courses`.`updated_at` = '2025-02-13 13:55:30' where `id` = 142
        310μs/app/Http/Controllers/CourseController.php:21corspedia
        Metadata
        Bindings
        • 0. 2025-02-13 13:55:30
        • 1. 142
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:21
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `topic_id`, `slug_en`, `slug_ar` from `subjects` where `subjects`.`id` in (6)
        220μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `slug_en`, `slug_ar` from `topics` where `topics`.`id` in (1)
        190μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 25. /app/Http/Controllers/CourseController.php:23
        • 26. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 27. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 28. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 29. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `institutions` where `institutions`.`id` in (19) and `institutions`.`deleted_at` is null
        220μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `providers` where `providers`.`id` in (2) and `providers`.`deleted_at` is null
        420μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `html_files` where `html_files`.`id` = 142 limit 1
        300μs/app/Models/Course.php:84corspedia
        Metadata
        Bindings
        • 0. 142
        Backtrace
        • 21. /app/Models/Course.php:84
        • 28. view::public.courses.show:29
        • 30. /vendor/laravel/framework/src/Illuminate/Filesystem/Filesystem.php:125
        • 31. /vendor/laravel/framework/src/Illuminate/View/Engines/PhpEngine.php:58
        • 32. /vendor/laravel/framework/src/Illuminate/View/Engines/CompilerEngine.php:72
      App\Models\HtmlFile
      1
      App\Models\Provider
      1
      App\Models\Institution
      1
      App\Models\Topic
      1
      App\Models\Subject
      1
      App\Models\Course
      1
        _token
        YK8o1PMlrQO6WZrIDWCVV2MWoRCyYEajByGa55lt
        locale
        en
        _previous
        array:1 [ "url" => "https://www.corspedia.com/en/courses/algorithms-on-graphs" ]
        _flash
        array:2 [ "old" => [] "new" => [] ]
        PHPDEBUGBAR_STACK_DATA
        []
        path_info
        /en/courses/algorithms-on-graphs
        status_code
        200
        
        status_text
        OK
        format
        html
        content_type
        text/html; charset=UTF-8
        request_query
        []
        
        request_request
        []
        
        request_headers
        0 of 0
        array:24 [ "sec-ch-ua-mobile" => array:1 [ 0 => "?0" ] "sec-ch-ua" => array:1 [ 0 => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" ] "cache-control" => array:1 [ 0 => "no-cache" ] "pragma" => array:1 [ 0 => "no-cache" ] "cdn-loop" => array:1 [ 0 => "cloudflare; loops=1" ] "priority" => array:1 [ 0 => "u=0, i" ] "upgrade-insecure-requests" => array:1 [ 0 => "1" ] "user-agent" => array:1 [ 0 => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" ] "cf-connecting-ip" => array:1 [ 0 => "3.14.145.69" ] "accept" => array:1 [ 0 => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" ] "sec-fetch-site" => array:1 [ 0 => "none" ] "cf-visitor" => array:1 [ 0 => "{"scheme":"https"}" ] "sec-fetch-mode" => array:1 [ 0 => "navigate" ] "sec-fetch-user" => array:1 [ 0 => "?1" ] "x-forwarded-proto" => array:1 [ 0 => "https" ] "cf-ipcountry" => array:1 [ 0 => "US" ] "accept-encoding" => array:1 [ 0 => "gzip, br" ] "sec-fetch-dest" => array:1 [ 0 => "document" ] "sec-ch-ua-platform" => array:1 [ 0 => ""Windows"" ] "x-forwarded-for" => array:1 [ 0 => "3.14.145.69" ] "cf-ray" => array:1 [ 0 => "91155102cb8f6185-ORD" ] "host" => array:1 [ 0 => "www.corspedia.com" ] "content-length" => array:1 [ 0 => "" ] "content-type" => array:1 [ 0 => "" ] ]
        request_server
        0 of 0
        array:50 [ "USER" => "www-data" "HOME" => "/var/www" "HTTP_SEC_CH_UA_MOBILE" => "?0" "HTTP_SEC_CH_UA" => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" "HTTP_CACHE_CONTROL" => "no-cache" "HTTP_PRAGMA" => "no-cache" "HTTP_CDN_LOOP" => "cloudflare; loops=1" "HTTP_PRIORITY" => "u=0, i" "HTTP_UPGRADE_INSECURE_REQUESTS" => "1" "HTTP_USER_AGENT" => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" "HTTP_CF_CONNECTING_IP" => "3.14.145.69" "HTTP_ACCEPT" => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" "HTTP_SEC_FETCH_SITE" => "none" "HTTP_CF_VISITOR" => "{"scheme":"https"}" "HTTP_SEC_FETCH_MODE" => "navigate" "HTTP_SEC_FETCH_USER" => "?1" "HTTP_X_FORWARDED_PROTO" => "https" "HTTP_CF_IPCOUNTRY" => "US" "HTTP_ACCEPT_ENCODING" => "gzip, br" "HTTP_SEC_FETCH_DEST" => "document" "HTTP_SEC_CH_UA_PLATFORM" => ""Windows"" "HTTP_X_FORWARDED_FOR" => "3.14.145.69" "HTTP_CF_RAY" => "91155102cb8f6185-ORD" "HTTP_HOST" => "www.corspedia.com" "REDIRECT_STATUS" => "200" "SERVER_NAME" => "corspedia.com" "SERVER_PORT" => "443" "SERVER_ADDR" => "141.95.147.152" "REMOTE_USER" => "" "REMOTE_PORT" => "16664" "REMOTE_ADDR" => "172.69.7.152" "SERVER_SOFTWARE" => "nginx/1.18.0" "GATEWAY_INTERFACE" => "CGI/1.1" "HTTPS" => "on" "REQUEST_SCHEME" => "https" "SERVER_PROTOCOL" => "HTTP/2.0" "DOCUMENT_ROOT" => "/var/www/corspedia/public" "DOCUMENT_URI" => "/index.php" "REQUEST_URI" => "/en/courses/algorithms-on-graphs" "SCRIPT_NAME" => "/index.php" "CONTENT_LENGTH" => "" "CONTENT_TYPE" => "" "REQUEST_METHOD" => "GET" "QUERY_STRING" => "" "SCRIPT_FILENAME" => "/var/www/corspedia/public/index.php" "PATH_INFO" => "" "FCGI_ROLE" => "RESPONDER" "PHP_SELF" => "/index.php" "REQUEST_TIME_FLOAT" => 1739454930.6363 "REQUEST_TIME" => 1739454930 ]
        request_cookies
        []
        
        response_headers
        0 of 0
        array:5 [ "content-type" => array:1 [ 0 => "text/html; charset=UTF-8" ] "cache-control" => array:1 [ 0 => "no-cache, private" ] "date" => array:1 [ 0 => "Thu, 13 Feb 2025 13:55:30 GMT" ] "set-cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IlA0Sk1uYUZwY3B1V0V2ZDE0YmYxaFE9PSIsInZhbHVlIjoiaXQzVzdjTW9iK3cxL2N1bk1aSHlqa2VXanNmdHVYa3d5cDVHMGFwYUsxemV5THc1M2dXM1Zqc0xJWURhQlRDQTNXWFZuaW5VZ3U2dWxNT1YzQzB5Ukxnd3dMU0tWbDNYTXRrVy9HZFhrU1Nramk0Y1RyeDAyVnQ0UU9FOXVmRmMiLCJtYWMiOiIwMzY3Yjg4ZDcxOTc2ODJiZGNkNjcxZjA2YjdlY2U0MmU5YmFlMzgxZmUzNGViNGVlNDQzNGVhMTUxMGEwMzMzIiwidGFnIjoiIn0%3D; expires=Thu, 13 Feb 2025 15:55:30 GMT; Max-Age=7200; path=/; samesite=laxXSRF-TOKEN=eyJpdiI6IlA0Sk1uYUZwY3B1V0V2ZDE0YmYxaFE9PSIsInZhbHVlIjoiaXQzVzdjTW9iK3cxL2N1bk1aSHlqa2VXanNmdHVYa3d5cDVHMGFwYUsxemV5THc1M2dXM1Zqc0xJWURhQlRDQTNXWFZua" 1 => "laravel_session=eyJpdiI6IlZ1NjNUZ3M0N3VUUys3OHFod3F4elE9PSIsInZhbHVlIjoiM0JLMHJDbEVadTVkb3hML1RxRXJRYzBuL3FVSDlmZCtKWEYxY3AyNjdrUENIQmZzUVR1c1BlU1ZZaXFZOTl5NGVTZDBzNElqaThsU3VpaEdKRTV4RlFBVEJqbTV2alFhZWh1UmZsdXB0RDJHQjdXT1BLT0ppUWU4eXVYTkF2SlQiLCJtYWMiOiI5MGJjZGVhODEyNWQ2NWMwMmVhYWQyNjliNjBhMTNkYWM2ODY5NTg0NDU2MjMzN2Q4MGVhNGI3Yzc2YTVmZWE0IiwidGFnIjoiIn0%3D; expires=Thu, 13 Feb 2025 15:55:30 GMT; Max-Age=7200; path=/; httponly; samesite=laxlaravel_session=eyJpdiI6IlZ1NjNUZ3M0N3VUUys3OHFod3F4elE9PSIsInZhbHVlIjoiM0JLMHJDbEVadTVkb3hML1RxRXJRYzBuL3FVSDlmZCtKWEYxY3AyNjdrUENIQmZzUVR1c1BlU1ZZaXFZOTl5NGVT" ] "Set-Cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IlA0Sk1uYUZwY3B1V0V2ZDE0YmYxaFE9PSIsInZhbHVlIjoiaXQzVzdjTW9iK3cxL2N1bk1aSHlqa2VXanNmdHVYa3d5cDVHMGFwYUsxemV5THc1M2dXM1Zqc0xJWURhQlRDQTNXWFZuaW5VZ3U2dWxNT1YzQzB5Ukxnd3dMU0tWbDNYTXRrVy9HZFhrU1Nramk0Y1RyeDAyVnQ0UU9FOXVmRmMiLCJtYWMiOiIwMzY3Yjg4ZDcxOTc2ODJiZGNkNjcxZjA2YjdlY2U0MmU5YmFlMzgxZmUzNGViNGVlNDQzNGVhMTUxMGEwMzMzIiwidGFnIjoiIn0%3D; expires=Thu, 13-Feb-2025 15:55:30 GMT; path=/XSRF-TOKEN=eyJpdiI6IlA0Sk1uYUZwY3B1V0V2ZDE0YmYxaFE9PSIsInZhbHVlIjoiaXQzVzdjTW9iK3cxL2N1bk1aSHlqa2VXanNmdHVYa3d5cDVHMGFwYUsxemV5THc1M2dXM1Zqc0xJWURhQlRDQTNXWFZua" 1 => "laravel_session=eyJpdiI6IlZ1NjNUZ3M0N3VUUys3OHFod3F4elE9PSIsInZhbHVlIjoiM0JLMHJDbEVadTVkb3hML1RxRXJRYzBuL3FVSDlmZCtKWEYxY3AyNjdrUENIQmZzUVR1c1BlU1ZZaXFZOTl5NGVTZDBzNElqaThsU3VpaEdKRTV4RlFBVEJqbTV2alFhZWh1UmZsdXB0RDJHQjdXT1BLT0ppUWU4eXVYTkF2SlQiLCJtYWMiOiI5MGJjZGVhODEyNWQ2NWMwMmVhYWQyNjliNjBhMTNkYWM2ODY5NTg0NDU2MjMzN2Q4MGVhNGI3Yzc2YTVmZWE0IiwidGFnIjoiIn0%3D; expires=Thu, 13-Feb-2025 15:55:30 GMT; path=/; httponlylaravel_session=eyJpdiI6IlZ1NjNUZ3M0N3VUUys3OHFod3F4elE9PSIsInZhbHVlIjoiM0JLMHJDbEVadTVkb3hML1RxRXJRYzBuL3FVSDlmZCtKWEYxY3AyNjdrUENIQmZzUVR1c1BlU1ZZaXFZOTl5NGVT" ] ]
        session_attributes
        0 of 0
        array:5 [ "_token" => "YK8o1PMlrQO6WZrIDWCVV2MWoRCyYEajByGa55lt" "locale" => "en" "_previous" => array:1 [ "url" => "https://www.corspedia.com/en/courses/algorithms-on-graphs" ] "_flash" => array:2 [ "old" => [] "new" => [] ] "PHPDEBUGBAR_STACK_DATA" => [] ]