minimum spanning tree + shortest path

Question 1

what is Dijkstra’s algorithm

Answer 1

single source shortest path

Find the shortest path from one node to all nodes, no negative edges allowed

greedy algorithm

Question 2

what is bellman-ford

Answer 2

find the shortest path from one node to all nodes, negative edges are allowed

dynamic programming alg

Question 3

what is floyd-warshall

Answer 3

find the shortest path between all nodes. negative edges are allowed

dynamic programming alg

Question 4

what is kruskals alg

Answer 4

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

Question 5

what is prims alg

Answer 5

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

Question 6

time complexity of prims alg

Answer 6

O (E log V), that is to say O(edges * log (vertices))

Question 7

time complexity of kruskals alg

Answer 7

O (E log E), that is to say O(edges * log(edges))

Question 8

when is a graph sparse, and when is it complete

Answer 8

• 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.

Question 9

when should prims be used and when should kruskals be used

Answer 9

• 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

Question 10

how to implement dijkstras

Answer 10

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.

Question 11

hows to implement bellman-ford

Answer 11

For each edge, relax (update) distances V−1 times. Detects negative cycles and works with negative weights. Finds shortest path.

Question 12

how to implement prims

Answer 12

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).

Question 13

how to implement kruskals

Answer 13

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.

Question 14

how to implement floyd-warshall

Answer 14

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.

Question 15

time complexity of bellman-ford

Answer 15

O(V * E)

Question 16

time complexity of dijkstras

Answer 16

O((V + E) * log (V))

Question 17

time and space complexity of floyd-warshall

Answer 17

time: O(n^3)
space: O(n^2)

Question 18

when should dijkstras be used, when should bellman-ford be used, and when should floyd-warshall be used

Answer 18

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.