LeetCode 150 Roadmap - Advanced Graphs Part 2 (Dijkstra's Algorithm, Topological Sort, Bellman-Ford)

Dijkstra's algorithm is a method for finding the shortest path between nodes in a graph, where each edge has a non-negative weight. It starts from a source node and explores the closest unvisited nodes first, updating the shortest distance to each node as it progresses. The algorithm maintains a priority queue of nodes sorted by their current shortest distance from the source. It repeatedly selects the node with the smallest distance, explores its neighbors, and updates their distances if a shorter path is found. This process continues until all reachable nodes have been visited.

Topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. It's often used in task scheduling, where tasks must be executed in a specific order with precedence constraints. The algorithm works by repeatedly selecting a vertex with no incoming edges, removing it from the graph, and adding it to the sorted order. This process continues until all vertices are removed.

Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph, even in the presence of negative weight edges, as long as there are no negative weight cycles reachable from the source. It iteratively relaxes edges, meaning it attempts to improve the shortest path estimate to each vertex by considering all possible edges. The algorithm performs this relaxation process for each vertex for a number of iterations equal to the number of vertices minus one, ensuring convergence to the shortest paths.

Questions covered in this video:
Swim In Rising Water: https://leetcode.com/problems/swim-in...
Alien Dictionary: https://neetcode.io/problems/foreign-...
Cheapest Flights Within K Stops: https://leetcode.com/problems/cheapes...

#interview #question #python #algorithm #datastructures #problem #solution #leeds #luckyleeds #graphtheory #graphs