Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach, always selecting the vertex with the smallest known distance.
Algorithm Dijkstra(G, source):
Initialize all distances to infinity
Set distance[source] = 0
Create priority queue Q with all vertices
while Q is not empty:
u = vertex in Q with minimum distance
remove u from Q
mark u as visited
for each neighbor v of u:
if distance[u] + weight(u,v) < distance[v]:
distance[v] = distance[u] + weight(u,v)
return distance array
Dijkstra's algorithm assumes that once a node is visited (has the minimum distance), that distance is final. With negative edges, a shorter path might be found later, but Dijkstra won't reconsider already-visited nodes.
A negative cycle is a cycle where the sum of edge weights is negative. With a negative cycle, you can keep going through the cycle repeatedly to make the path cost arbitrarily negative (approaching -∞). The shortest path problem becomes undefined!
A Minimum Spanning Tree (MST) connects all vertices in a weighted graph with the minimum total edge weight, forming a tree (no cycles) with exactly n-1 edges for n vertices.
Grows the MST from a starting vertex by repeatedly adding the minimum-weight edge connecting the tree to a new vertex.
Algorithm Prim(G):
MST = empty set
Start with arbitrary vertex
while MST has fewer than n-1 edges:
find minimum-weight edge connecting
tree to a new vertex
add edge to MST
return MST
Sorts all edges by weight and adds them one by one, skipping edges that would create a cycle. Uses Union-Find data structure.
Algorithm Kruskal(G):
MST = empty set
Sort all edges by weight
Initialize Union-Find structure
for each edge (u,v) in sorted order:
if u and v are in different components:
add (u,v) to MST
union(u, v)
return MST