\(\newcommand{\SPDist}[2]{\delta(#1,#2)}\)
\(\newcommand{\SPEst}[1]{{#1}.\textrm{dist}}\)
\(\newcommand{\SPPred}[1]{{#1}.\textrm{pred}}\)
\(\newcommand{\SPNil}{\textbf{nil}}\)
\(\newcommand{\SPSrc}{s}\)
\(\newcommand{\SPTgt}{t}\)
\(\)
\(\newcommand{\Weights}{w}\)
\(\newcommand{\Weight}[2]{w(#1,#2)}\)
\(\newcommand{\UWeights}{w}\)
\(\newcommand{\UWeight}[2]{w(\Set{#1,#2})}\)
\(\)
\(\newcommand{\MSTCand}{A}\)
\(%\newcommand{\UFMS}[1]{\textsc{make-set}(#1)}\)
\(%\newcommand{\UFFS}[1]{\textsc{find-set}(#1)}\)
\(%\newcommand{\UFUnion}[2]{\textsc{union}(#1,#2)}\)
\(\)
\(\newcommand{\MSTParent}[1]{{#1}.\textsf{parent}}\)
\(\newcommand{\MSTNil}{\textbf{nil}}\)
\(\newcommand{\MSTKey}[1]{{#1}.\textsf{key}}\)
\(\newcommand{\MSTRoot}{\mathit{root}}\)
\(\)
Round 8: Graphs, part II
In this round, we continue on graph algorithms.
We now consider edge-weighted graphs that appear in many applications
and
show how some elementary problems on them can be solved algorithmically.
Material in Introduction to Algorithms, 3rd ed. (online via Aalto lib):
Some external links: