algorithms Flashcards
Prim’s heap
- Use a heap of vertices in S. The key of a vertex v is the weight of the minimum-weight edge connecting v to S.
- When a new vertex y is added to S, update the keys of vertices adjacent to y. This update happens at most m times in total
- n inserts,
- n extract-mins,
- m decrease-keys
- total: O(mlogn)
Prim’s naive
n -1 iterations
In each iteration, look through all edges to find min-weight edge crossing the cut - O(m) time
=> O(mn)
Kruskal’s naive
sorting O(mlogn)
m iterations: at each BFS/DFS to check if the endpoints are already connected - O(m+n) per iteration => m(m+n)
=> O(m^2 + n)
Kruskal’s union find
sorting O(mlogn)
Union-Find Operations:
- n Make-Set operations, one for each vertex
- 2m find operations, one for each endpoint of each edge
- n − 1 Union operations, one for each edge added to A
- Using a Union-Find implementation based on trees with path compression and union by rank: O(m + n log n)
=> Total time: O(m log n)
Dijkstra’s list
- Keep d(u) values in an adjacency list
- Selecting the minimum dˆ value takes O(n) time, happens n times - select the vertex with min d^
- decreases dˆ values at most once per relaxation, which occurs at most m times
- Total time: O(n^2 + m) = O(n^2)
Dijkstra’s heap
- Insert n times
- Extract-Min n times
- Decrease-Key m times
- Using a binary heap: O(log n) per operation
- Total time: O((m + n) log n)
Ford-Fulkerson correctness
The correctness of the Ford-Fulkerson algorithm follows directly from the Max-Flow Min-Cut Theorem and the analysis of residual graphs:
* The algorithm terminates when there are no augmenting paths in Gf .
* By the proof of the Max-Flow Min-Cut Theorem, at this point, f is a maximum (s,t)-flow, and the value of the flow |f|
equals the capacity of a minimum (s, t)-cut.
Edmonds-Karp #1
- Total iterations: O(m ln F )
- Time per iteration: O(m log n)
- Total time: O(m log n · m ln F ) = O(m^2 log n log F )
Edmonds-Karp #2
- Each iteration uses BFS to find the shortest path in O(m + n) time.
- Total number of iterations: O(mn)
- Total Running Time: O(mn · (m + n)) = O(m^2n), which is independent of F
Prim’s correctness
Prim’s algorithm constructs a Minimum Spanning Tree (MST) by repeatedly adding the lightest edge that connects a vertex in the growing tree to a vertex outside of it. The correctness is established through the cut property: each edge added is the light edge crossing the cut separating the tree from the rest of the graph, ensuring that no cycles are created and the tree remains minimal in weight.
Kruskal’s correctness
Kruskal’s algorithm builds an MST by sorting all edges and adding the smallest edge that does not form a cycle (using a union-find structure). The correctness follows from the cut property as well, as the lightest edge across the cut (between connected components) is added, preserving the minimality of the spanning tree until all vertices are included.
Bellman-Ford correctness
The Bellman-Ford algorithm calculates shortest paths from a single source vertex to all other vertices by repeatedly relaxing all edges. Its correctness is guaranteed through dynamic programming and the principle of optimal substructure: after ( k ) iterations, it accurately computes the shortest path using at most ( k ) edges, reaching a maximum of ( n-1 ) iterations (where ( n ) is the number of vertices).
Floyd-Warshall correctness
The correctness is confirmed because after ( n ) iterations (with ( n ) being the number of vertices), all pairs’ shortest paths are guaranteed to be computed accurately. It ensures that, after considering all vertices as possible intermediate points, the shortest path values ( D[i][j] ) yield the actual shortest distances between all pairs of vertices in the graph.
Ford-Fulkerson correctness
The correctness of the Ford-Fulkerson algorithm follows directly from the Max-Flow Min-Cut Theorem and the analysis of residual graphs:
* The algorithm terminates when there are no augmenting paths in Gf .
* By the proof of the Max-Flow Min-Cut Theorem, at this point, f is a maximum (s,t)-flow, and the value of the flow |f|
equals the capacity of a minimum (s, t)-cut.
The Ford-Fulkerson algorithm computes the maximum flow in a flow network by finding augmenting paths in the residual graph. The correctness is derived from the Max-Flow Min-Cut Theorem: when no more augmenting paths exist, the flow is maximized, and its value equals the capacity of the minimum cut separating the source and sink.
