Design of Algorithms

Greedy Algorithms

Greedy Algorithms

Table of Contents

Overview

Minimum Spanning Tree Problem

Prim’s Algorithm

Prim(G)
# Prim's algorithm for constructing minimum spanning tree
# Input: weight graph G=<V,E>
# Output: E_T, set of edges composing minimum spanning tree of G
V_T = {v_0} # arbitrary vertex
E_T = empty_set
for i from 1 to |V|-1:
    find minimum weight edge e* = (v*, u*) among all edges (v, u), such that v is in V_T, 
    and u is in V-V_T
    V_T = union(V_T, u*)
    E_T = union(E_T, e*)
return E_T

Dijkstra’s Algorithm




Edit this page.