Graph Algorithms

Dijskstra’s Algorithm  finds the shortest path from a single node to every other node

It is a greedy algorithm (similar to Prim’s algorithm)

 

Topological Sort

Motivating Example (reference)figure23_7

 

Topological Sorting

 

Minimum Spanning Tree

Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together

 

References

Greedy Algorithms | Set 5 (Prim’s Minimum Spanning Tree (MST))

Greedy Algorithms | Set 2 (Kruskal’s Minimum Spanning Tree Algorithm)