CPSC 2120 - DAY 15
JUNE 6, 2016

================================================================================

SHORTEST PATH ALGORITHM
-----------------------

Dijkstra's Algorithm

Single Source - Multiple Destination

REQUIREMENTS

Works with directed and undirected graphs
Works with weighted and unweighted graphs

Rare type of algorithm

A greedy algorithm that produces an optimal solution

find Min takes O(V) time
outer loop iterates (V-1) times

Optimal for dense graphs i.e. |E| = O(V^2)
Suboptimal for sparse graphs i.e. |E| = O(V)

Fastest Algorithm for finding minimum distances


MINIMUM SPANNING TREES
----------------------

PRIM AND KRUSKALS ALGORITHM

A minimum spanning tree is a subgraph of an undirected graph such that the 
subgraph spans all nodes, is connected, is acyclic, and has minimum total edge
weight

Produces a tree that spans all nodes at minimum cost

Kruskal's Algorithm

Works with edges, rather than nodes

Two Steps:
	Sort edges by increasing edge weight
	Select the first |V| -1 edges that do not generate a cycle.

Only select the edges that will not create a cycle within the graph