minimum spanning tree + shortest path Flashcards
what is Dijkstra’s algorithm
single source shortest path
Find the shortest path from one node to all nodes, no negative edges allowed
greedy algorithm
what is bellman-ford
find the shortest path from one node to all nodes, negative edges are allowed
dynamic programming alg
what is floyd-warshall
find the shortest path between all nodes. negative edges are allowed
dynamic programming alg
what is kruskals alg
finds a minimum spanning tree
order the edges by least weight to greatest. then iterate through the list, always picking the next shortest edge that doesn’t create a cycle
greedy alg
what is prims alg
finds a minimum spanning tree
uses the cut method, pick a random node and pick the next shortest edge connected to a connected node that doesn’t create a cycle
greedy alg
time complexity of prims alg
O (E log V), that is to say O(edges * log (vertices))
time complexity of kruskals alg
O (E log E), that is to say O(edges * log(edges))
when is a graph sparse, and when is it complete
- In a sparse graph: E≈V
- In a dense graph: E can be as large as V2
^^^^That seems like a really hard target to hit…..
A graph is complete when every two vertices/nodes are directly connected by an edge. Near-complete is similar, just that almost all are directly connected instead of requiring that every single pair be directly connected.
when should prims be used and when should kruskals be used
- If the graph is complete or nearly complete, Prim performs
faster O(ElogV) - In Kruskal: If the graph is sparse (few edges), Kruskal gives
O(ElogE)
so, the more edges the more of an advantage prims has
how to implement dijkstras
Use a priority queue to repeatedly select the closest unvisited node, update its neighbors’ distances, and mark it as visited. Best for shortest paths in non-negative weight graphs.
hows to implement bellman-ford
For each edge, relax (update) distances V−1 times. Detects negative cycles and works with negative weights. Finds shortest path.
how to implement prims
Start from any node and add the shortest edge connecting the growing tree to a new node until all nodes are included. This creates Minimum Spanning Trees (MSTs).
how to implement kruskals
Sort all edges by weight, and use a union-find structure to add the shortest edge to the MST without creating cycles, until all nodes are connected.
how to implement floyd-warshall
Use a 2D matrix to update all pairs’ shortest paths by considering each node as an intermediate, one-by-one. Good for finding shortest paths in dense graphs.
time complexity of bellman-ford
O(V * E)
time complexity of dijkstras
O((V + E) * log (V))
time and space complexity of floyd-warshall
time: O(n^3)
space: O(n^2)
when should dijkstras be used, when should bellman-ford be used, and when should floyd-warshall be used
Dijkstra’s:
Use it when you need the shortest path from a single source, the graph has non-negative weights, and you want efficient performance (works best with sparse graphs).
Bellman-Ford:
Use it when you need the shortest path from a single source and the graph has negative weights or may have negative cycles. It’s slower but can handle scenarios Dijkstra’s can’t.
Floyd-Warshall:
Use it when you need shortest paths between all pairs of nodes, regardless of edge weights (though no negative cycles). It’s most suitable for dense graphs or smaller graphs, as it has a high time complexity.
