Dijkstra's Algorithm
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding shortest distances from a source in a weighted, undirected, connected graph using Dijkstra's Algorithm, Graph, Weighted Graph, Undirected Graph, Adjacency List, Graph Traversal, Distance Calculation, Algorithm, Set, Heap/Priority Queue, Time Complexity, Space Complexity, graph representation, complexity analysis, priority queue, dijkstra's algorithm, set, shortest path algorithms, graph, graph properties, Graph Types, Shortest Path (Dijkstra's Algorithm), Heap (Priority Queue).
Given a weighted, undirected, and connected graph with V vertices, represented by an adjacency list adj where adj[i] contains lists [j, weight] indicating an edge between vertex i and vertex j with a given weight. You are also given a source vertex S. Your task is to find the shortest distance from the source vertex S to all other vertices in the graph. Return a list of integers, where the i th element denotes the shortest distance between vertex i and the source vertex S. Note: The graph does not contain any negative weight cycles. Input: V: An integer, the number of vertices in the graph. adj: An adjacency list, adj[i] is a list of lists containing two integers [j, weight], representing an edge from i to j with weight. S: An integer, the source vertex. Output: A list of integers, where result[i] is the shortest distance from S to vertex i. Example 1: Input: V = 2 adj = {{{1, 9}}, {{0, 9}}} S = 0 Output: 0 9 Explanation: The source vertex is 0. The shortest distance from node 0 to itself is 0. The shortest distance from node 0 to node 1 is 9 (via the direct edge). Example 2: Input: V = 3 adj = {{{1, 1}, {2, 6}}, {{2, 3}, {0, 1}}, {{1, 3}, {0, 6}}} S = 2 Output: 4 3 0 Explanation: For nodes 2 to 0: The path 2 1 0 has a total distance of 3 (from 2 to 1) + 1 (from 1 to 0) = 4. The path 2 0 has a distance of 6. Thus, the shortest path from 2 to 0 is 4. For nodes 2 to 1: The direct path 2 1 has a distance of 3. Thus, the shortest path from 2 to 1 is 3. For nodes 2 to 2: The shortest distance from node 2 to itself is 0.