For a DAG with V vertices and E edges, single-source shortest paths can be computed in:
Process vertices in topological order and relax each edge once.
Bellman-Ford is preferred over Dijkstra when a graph may contain:
Bellman-Ford handles negative edge weights and can detect a reachable negative-weight cycle.
Suppose Bellman-Ford performs V-1 complete relaxation passes and then finds an edge (u,v) satisfying d[v] > d[u] + w(u,v). What does this imply?
After V-1 passes, any further relaxation indicates a reachable negative cycle.
In a connected weighted undirected graph, if an edge e is the unique lightest edge crossing some cut, then e:
The cut property states that the unique minimum-weight edge crossing a cut is present in every MST.
Kruskal’s algorithm can be implemented efficiently using which data structure to detect whether an edge creates a cycle?
DSU maintains connected components and supports efficient FIND and UNION operations.