Bellman-Ford Algorithm
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Bellman-Ford Algorithm for Single-Source Shortest Path in Directed Weighted Graphs (including with Negative Edge Weights and Negative Cycles), Graph, Weighted Graph, Directed Graph, Edge, Shortest Path, Distance Calculation, Cycle Detection, Time Complexity, Space Complexity, Dijkstra's Algorithm, Bellman-Ford Algorithm, complexity analysis, graph algorithms, visited tracking, bellman-ford algorithm, shortest path algorithms, graph properties, cycle detection, Shortest Path (Dijkstra's Algorithm), Graph Types, Shortest Path (Bellman-Ford).
Problem Statement: Given a weighted, directed, and connected graph with V vertices and E edges, find the shortest distance of all vertices from a given source vertex S. Note: If the graph contains a negative cycle, return an array consisting of only 1. Input Format: V: An integer representing the number of vertices. E: A list of lists, where each inner list [u, v, wt] represents a directed edge from vertex u to vertex v with weight wt. S: An integer representing the source vertex. Output Format: Return an array of integers dist, where dist[i] is the shortest distance from the source S to vertex i. If a negative cycle is detected, return an array containing a single element, 1. Example 1: Input: V = 6, E = [[3, 2, 6], [5, 3, 1], [0, 1, 5], [1, 5, 3], [1, 2, 2], [3, 4, 2], [2, 4, 3]], S = 0 Result: 0 5 3 3 1 2 Explanation: Shortest distance of all nodes from the source node is returned. Example 2: Input: V = 2, E = [[0,1,9]], S = 0 Result: 0 9 Explanation: Shortest distance of all nodes from the source node is returned.