Dijkstra's Shortest Path Algorithm | Graph Theory

WilliamFiset · Beginner ·📰 AI News & Updates ·7y ago

Algorithm Basics80%Graph Algorithms70%

Explanation of Dijkstra's shortest path algorithm Dijkstra source code on Algorithms repository: https://github.com/williamfiset/algorithms#graph-theory Video slides: https://github.com/williamfiset/Algorithms/tree/master/slides Indexed Priority Queue Video: https://youtu.be/jND_WJ8r7FE 0:00 Intro 0:28 What is Dijkstra's algorithm? 1:13 Algorithm prerequisites 1:55 Video outline 2:28 Dijkstra's algorithm overview 3:50 Lazy Dijkstra's animation 8:10 Lazy Dijkstra's code 11:33 Ignoring stale node optimization 12:11 Finding the shortest path 14:01 Stopping early optimization 15:11 Eager Dijks…

Watch on YouTube ↗ (saves to browser)

Chapters (15)

Intro

0:28 What is Dijkstra's algorithm?

1:13 Algorithm prerequisites

1:55 Video outline

2:28 Dijkstra's algorithm overview

3:50 Lazy Dijkstra's animation

8:10 Lazy Dijkstra's code

11:33 Ignoring stale node optimization

12:11 Finding the shortest path

14:01 Stopping early optimization

15:11 Eager Dijkstra's with an indexed priority queue

16:27 Eager Dijkstra's animation

19:28 Eager Dijkstra's code

20:31 D-ary heap optimization

23:06 The current state of the art for heaps

Playlist

Uploads from WilliamFiset · WilliamFiset · 0 of 60

← Previous Next →

JES Image Manipulation - 2 - Installation

JES Image Manipulation - 2 - Installation

JES Image Manipulation - 3 - User Interface

JES Image Manipulation - 3 - User Interface

JES Image Manipulation - 5 - Negative

JES Image Manipulation - 5 - Negative

JES Image Manipulation - 6 - Black & White

JES Image Manipulation - 6 - Black & White

JES Image Manipulation - 4 - Grayscale

JES Image Manipulation - 4 - Grayscale

JES Image Manipulation - 8 - Blur

JES Image Manipulation - 8 - Blur

JES Image Manipulation - 7 - Edge Detection

JES Image Manipulation - 7 - Edge Detection

JES Image Manipulation - 9 - Blend

JES Image Manipulation - 9 - Blend

JES Image Manipulation - 10 - Matte

JES Image Manipulation - 10 - Matte

JES Image Manipulation - 13 - Rotate90

JES Image Manipulation - 13 - Rotate90

JES Image Manipulation - 12 - Mirroring Picture

JES Image Manipulation - 12 - Mirroring Picture

JES Image Manipulation - 11 - Crop Image

JES Image Manipulation - 11 - Crop Image

JES Image Manipulation - 14 - Stretch picture

JES Image Manipulation - 14 - Stretch picture

Java Fractal Explorer [6/8]

Java Fractal Explorer [6/8]

Java Fractal Explorer [4/8]

Java Fractal Explorer [4/8]

Java Fractal Explorer [8/8]

Java Fractal Explorer [8/8]

Java Fractal Explorer [5/8]

Java Fractal Explorer [5/8]

Java Fractal Explorer [2/8]

Java Fractal Explorer [2/8]

Java Fractal Explorer [7/8]

Java Fractal Explorer [7/8]

Java Fractal Explorer [1/8]

Java Fractal Explorer [1/8]

Java Fractal Explorer [3/8]

Java Fractal Explorer [3/8]

Introduction [Programming Competition Problems]

Introduction [Programming Competition Problems]

String Manipulation 1 [Programming Competition Problems]

String Manipulation 1 [Programming Competition Problems]

String Manipulation 2 [Programming Competition Problems]

String Manipulation 2 [Programming Competition Problems]

Graph Theory 1 [Programming Competition Problems]

Graph Theory 1 [Programming Competition Problems]

Logic 1 [Programming Competition Problems]

Logic 1 [Programming Competition Problems]

Grid Problems 1 [Programming Competition Problems]

Grid Problems 1 [Programming Competition Problems]

Dynamic Programming 1 [Programming Competition Problems]

Dynamic Programming 1 [Programming Competition Problems]

Introduction to Big-O

Introduction to Big-O

Dynamic and Static Arrays

Dynamic and Static Arrays

Dynamic Array Code

Dynamic Array Code

Linked Lists Introduction

Linked Lists Introduction

Doubly Linked List Code

Doubly Linked List Code

Stack Introduction

Stack Introduction

Stack Implementation

Stack Implementation

Queue Introduction

Queue Introduction

Queue Implementation

Queue Implementation

Priority Queue Introduction

Priority Queue Introduction

Priority Queue Min Heaps and Max Heaps

Priority Queue Min Heaps and Max Heaps

Priority Queue Inserting Elements

Priority Queue Inserting Elements

Priority Queue Removing Elements

Priority Queue Removing Elements

Priority Queue Code

Priority Queue Code

Union Find Introduction

Union Find Introduction

Union Find Kruskal's Algorithm

Union Find Kruskal's Algorithm

Union Find - Union and Find Operations

Union Find - Union and Find Operations

Union Find Path Compression

Union Find Path Compression

Union Find Code

Union Find Code

Binary Search Tree Introduction

Binary Search Tree Introduction

Binary Search Tree Insertion

Binary Search Tree Insertion

Binary Search Tree Removal

Binary Search Tree Removal

Binary Search Tree Traversals

Binary Search Tree Traversals

Binary Search Tree Code

Binary Search Tree Code

Fenwick Tree range queries

Fenwick Tree range queries

Fenwick Tree point updates

Fenwick Tree point updates

Fenwick Tree construction

Fenwick Tree construction

Fenwick tree source code

Fenwick tree source code

Hash table hash function

Hash table hash function

Hash table separate chaining

Hash table separate chaining

Climate change and Indigenous People and local communities