#### MSP minimum spanning tree

Kruskal's algorithm

Kruskal's algorithm:

- sort the edges of G in increasing order by length
- keep a subgraph S of G, initially empty
- for each edge e in sorted order
- if the endpoints of e are disconnected in S
- add e to S

return S

This algorithm is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to S. You should be very careful when trying to use greedy

algorithms to solve other problems, since it usually doesn't work. E.g. if you want to find a shortest path from a to b, it might be a bad idea to keep taking the shortest edges. The

greedy idea only works in Kruskal's algorithm because of the key property we proved.

#### shortest path

##### shortest path problem from node v to t

- using BFS

This only applicable to graph with unweighted edges, simply do BFS from start node to

end node, and stop the search when it encounters the first occurrence of end node.

- dynamic programming for weighted edges

the predecessor sub-graph - the list of predecessors of each node, pi[j], 1 <= j <= |V|

##### Dijkstra's algorithm

Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can

find the shortest paths from a given source to all points in a graph in the same time, hence this problem is called the **Single-source shortest paths problem**.

For a graph, G=(V,E) where V is a set of vertices and E is a set of edges.

Dijkstra's algorithm keeps

- two sets of vertices: S (the set of vertices whose shortest paths from the source have already been determined) and V-S (the remaining vertices).
- The other data structures needed are: d (array of best estimates of shortest path to each vertex) & pi (an array of predecessors for each vertex)

```
DIJKSTRA(Graph G,Node s)
initialize_single_source(G,s)
S:={ 0 } /* Make S empty */
Q:=Vertices(G) /* Put the vertices in a PQ */
while not Empty(Q)
u:=ExtractMin(Q);
AddNode(S,u); /* Add u to S */
for each vertex v which is Adjacent with u
relax(u,v,w)
```

## Post preview:

Close preview