\(\)
\(%\newcommand{\CLRS}{\href{https://mitpress.mit.edu/books/introduction-algorithms}{Cormen et al}}\)
\(\newcommand{\CLRS}{\href{https://mitpress.mit.edu/books/introduction-algorithms}{Introduction to Algorithms, 3rd ed.} (\href{http://libproxy.aalto.fi/login?url=http://site.ebrary.com/lib/aalto/Doc?id=10397652}{Aalto access})}\)
\(%\newcommand{\CLRS}{\href{https://mitpress.mit.edu/books/introduction-algorithms}{Introduction to Algorithms, 3rd ed.} (\href{http://libproxy.aalto.fi/login?url=http://site.ebrary.com/lib/aalto/Doc?id=10397652}{online via Aalto lib})}\)
\(\newcommand{\SW}{\href{http://algs4.cs.princeton.edu/home/}{Algorithms, 4th ed.}}\)
\(%\newcommand{\SW}{\href{http://algs4.cs.princeton.edu/home/}{Sedgewick and Wayne}}\)
\(\)
\(\newcommand{\Java}{\href{http://java.com/en/}{Java}}\)
\(\newcommand{\Python}{\href{https://www.python.org/}{Python}}\)
\(\newcommand{\CPP}{\href{http://www.cplusplus.com/}{C++}}\)
\(\newcommand{\ST}[1]{{\Blue{\textsf{#1}}}}\)
\(\newcommand{\PseudoCode}[1]{{\color{blue}\textsf{#1}}}\)
\(\)
\(%\newcommand{\subheading}[1]{\textbf{\large\color{aaltodgreen}#1}}\)
\(\newcommand{\subheading}[1]{\large{\usebeamercolor[fg]{frametitle} #1}}\)
\(\)
\(\newcommand{\Blue}[1]{{\color{flagblue}#1}}\)
\(\newcommand{\Red}[1]{{\color{aaltored}#1}}\)
\(\newcommand{\Emph}[1]{\emph{\color{flagblue}#1}}\)
\(\)
\(\newcommand{\Engl}[1]{({\em engl.}\ #1)}\)
\(\)
\(\newcommand{\Pointer}{\raisebox{-1ex}{\huge\ding{43}}\ }\)
\(\)
\(\newcommand{\Set}[1]{\{#1\}}\)
\(\newcommand{\Setdef}[2]{\{{#1}\mid{#2}\}}\)
\(\newcommand{\PSet}[1]{\mathcal{P}(#1)}\)
\(\newcommand{\Card}[1]{{\vert{#1}\vert}}\)
\(\newcommand{\Tuple}[1]{(#1)}\)
\(\newcommand{\Implies}{\Rightarrow}\)
\(\newcommand{\Reals}{\mathbb{R}}\)
\(\newcommand{\Seq}[1]{(#1)}\)
\(\newcommand{\Arr}[1]{[#1]}\)
\(\newcommand{\Floor}[1]{{\lfloor{#1}\rfloor}}\)
\(\newcommand{\Ceil}[1]{{\lceil{#1}\rceil}}\)
\(\newcommand{\Path}[1]{(#1)}\)
\(\)
\(%\newcommand{\Lg}{\lg}\)
\(\newcommand{\Lg}{\log_2}\)
\(\)
\(\newcommand{\BigOh}{O}\)
\(%\newcommand{\BigOh}{\mathcal{O}}\)
\(\newcommand{\Oh}[1]{\BigOh(#1)}\)
\(\)
\(\newcommand{\todo}[1]{\Red{\textbf{TO DO: #1}}}\)
\(\)
\(\newcommand{\NULL}{\textsf{null}}\)
\(\)
\(\newcommand{\Insert}{\ensuremath{\textsc{insert}}}\)
\(\newcommand{\Search}{\ensuremath{\textsc{search}}}\)
\(\newcommand{\Delete}{\ensuremath{\textsc{delete}}}\)
\(\newcommand{\Remove}{\ensuremath{\textsc{remove}}}\)
\(\)
\(\newcommand{\Parent}[1]{\mathop{parent}(#1)}\)
\(\)
\(\newcommand{\ALengthOf}[1]{{#1}.\textit{length}}\)
\(\)
\(\newcommand{\TRootOf}[1]{{#1}.\textit{root}}\)
\(\newcommand{\TLChildOf}[1]{{#1}.\textit{leftChild}}\)
\(\newcommand{\TRChildOf}[1]{{#1}.\textit{rightChild}}\)
\(\newcommand{\TNode}{x}\)
\(\newcommand{\TNodeI}{y}\)
\(\newcommand{\TKeyOf}[1]{{#1}.\textit{key}}\)
\(\)
\(\newcommand{\PEnqueue}[2]{{#1}.\textsf{enqueue}(#2)}\)
\(\newcommand{\PDequeue}[1]{{#1}.\textsf{dequeue}()}\)
\(\)
\(\newcommand{\Def}{\mathrel{:=}}\)
\(\)
\(\newcommand{\Eq}{\mathrel{=}}\)
\(\newcommand{\Asgn}{\mathrel{\leftarrow}}\)
\(%\newcommand{\Asgn}{\mathrel{:=}}\)
\(\)
\(%\)
\(% Heaps\)
\(%\)
\(\newcommand{\Downheap}{\textsc{downheap}}\)
\(\newcommand{\Upheap}{\textsc{upheap}}\)
\(\newcommand{\Makeheap}{\textsc{makeheap}}\)
\(\)
\(%\)
\(% Dynamic sets\)
\(%\)
\(\newcommand{\SInsert}[1]{\textsc{insert}(#1)}\)
\(\newcommand{\SSearch}[1]{\textsc{search}(#1)}\)
\(\newcommand{\SDelete}[1]{\textsc{delete}(#1)}\)
\(\newcommand{\SMin}{\textsc{min}()}\)
\(\newcommand{\SMax}{\textsc{max}()}\)
\(\newcommand{\SPredecessor}[1]{\textsc{predecessor}(#1)}\)
\(\newcommand{\SSuccessor}[1]{\textsc{successor}(#1)}\)
\(\)
\(%\)
\(% Union-find\)
\(%\)
\(\newcommand{\UFMS}[1]{\textsc{make-set}(#1)}\)
\(\newcommand{\UFFS}[1]{\textsc{find-set}(#1)}\)
\(\newcommand{\UFCompress}[1]{\textsc{find-and-compress}(#1)}\)
\(\newcommand{\UFUnion}[2]{\textsc{union}(#1,#2)}\)
\(\)
\(\)
\(%\)
\(% Graphs\)
\(%\)
\(\newcommand{\Verts}{V}\)
\(\newcommand{\Vtx}{v}\)
\(\newcommand{\VtxA}{v_1}\)
\(\newcommand{\VtxB}{v_2}\)
\(\newcommand{\VertsA}{V_\textup{A}}\)
\(\newcommand{\VertsB}{V_\textup{B}}\)
\(\newcommand{\Edges}{E}\)
\(\newcommand{\Edge}{e}\)
\(\newcommand{\NofV}{\Card{V}}\)
\(\newcommand{\NofE}{\Card{E}}\)
\(\newcommand{\Graph}{G}\)
\(\)
\(\newcommand{\SCC}{C}\)
\(\newcommand{\GraphSCC}{G^\text{SCC}}\)
\(\newcommand{\VertsSCC}{V^\text{SCC}}\)
\(\newcommand{\EdgesSCC}{E^\text{SCC}}\)
\(\)
\(\newcommand{\GraphT}{G^\text{T}}\)
\(%\newcommand{\VertsT}{V^\textup{T}}\)
\(\newcommand{\EdgesT}{E^\text{T}}\)
\(\)
\(%\)
\(% NP-completeness etc\)
\(%\)
\(\newcommand{\Poly}{\textbf{P}}\)
\(\newcommand{\NP}{\textbf{NP}}\)
\(\newcommand{\PSPACE}{\textbf{PSPACE}}\)
\(\newcommand{\EXPTIME}{\textbf{EXPTIME}}\)
\(\newcommand{\Graph}{G}\)
\(\newcommand{\Verts}{V}\)
\(\newcommand{\Vtx}{v}\)
\(\newcommand{\Edges}{E}\)
\(\newcommand{\Path}[1]{(#1)}\)
\(\)
\(\newcommand{\GColor}[1]{{#1}.\textrm{color}}\)
\(\newcommand{\GWhite}{\textbf{white}}\)
\(\newcommand{\GGray}{\textbf{gray}}\)
\(\newcommand{\GBlack}{\textbf{black}}\)
\(\newcommand{\GDist}[1]{{#1}.\text{dist}}\)
\(\newcommand{\GPred}[1]{{#1}.\text{pred}}\)
\(\newcommand{\GNil}{\textbf{nil}}\)
\(\newcommand{\GTime}{\textit{time}}\)
\(\newcommand{\GStart}[1]{{#1}.\text{start}}\)
\(\newcommand{\GFinish}[1]{{#1}.\text{finish}}\)
\(\newcommand{\GraphP}{G_\text{pred}}\)
\(\newcommand{\EdgesP}{E_\text{pred}}\)
\(\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}}\)
\(\)
Edge-weighted graphs
In many applications,
the edges in the graphs have some numeric weight/length/cost/etc
associated to them.
For instance, if a graph models a road map, then
the vertices are road crossings and endings,
the edges are roads connecting these, and
the edges are labeled with the length of road (i.e., the distance between the two points).
In a social network model,
the edge weights could represent the number of messages exchanged
between the connected people during the last month.
In the abstract mathematical level,
we call such numeric values on edges as weights.
In the following,
we extend the mathematical definitions for graphs (recall Section Mathematical definitions) to allow edge weights.
An edge-weighted undirected graph is a triple
\[\Tuple{\Verts,\Edges,\UWeights},\]
where
\(\Verts\) is a (usually finite) set of vertices,
\(\Edges\) is a set of edges between the vertices,
each edge being a pair of the form \(\Set{u,v}\)
with \(u,v \in \Verts\) and \(u \neq v\), and
\(\UWeights: \Edges \to \Reals\) associates a real-valued weight to each edge.
Example
The graph shown below is \(\Tuple{\Verts,\Edges,\UWeights}\), where
the vertices are \(\Verts = \Set{a,b,c,d,e,f,g}\),
the edges are \(\Edges = \{\Set{a,b},\Set{a,e},\Set{a,f},\Set{b,c},\Set{b,d},\Set{b,f},\Set{c,d},\Set{c,e},\Set{d,g},\Set{e,f}\}\), and
the weights are \(\UWeight{a}{b} = 7\), \(\UWeight{a}{e} = 6\) and so on.
The edge-weighted directed graphs are defined similarly
except that the edges are pairs of form \(\Tuple{u,v} \in \Verts \times \Verts\)
as in the case of directed graphs without edge weights.
Paths, cycles, and trees are defined in the same way as for the graphs without edge weights.