\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pstricks}
\usepackage{multicol}



\begin{document}

\title{Episode 22 -- The shortest path problem}
\subtitle{European section -- Season 2}
\date{}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}{A weighted graph}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2,-2)(11,4)
\psline(3.22,3.02)(0.32,1.18)
\psline(0.32,1.18)(3.46,-0.48)
\psline(3.46,-0.48)(6.44,1.86)
\psline(6.44,1.86)(3.22,3.02)
\rput[tl](1.52,2.4){2}
\rput[tl](1.86,0.24){3}
\rput[tl](4.82,2.84){5}
\rput[tl](5.16,0.74){6}
\uput[l](0.32,1.18){A}
\uput[u](3.22,3.02){B}
\uput[d](3.46,-0.48){C}
\uput[r](6.44,1.86){D}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.32,1.18)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.22,3.02)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.46,-0.48)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.44,1.86)
\end{pspicture*}
\end{center}

\end{frame}

\begin{frame}{The shortest path problem}

\begin{center}
\includegraphics[width=10cm]{s02e22/latony.eps}
\end{center}

\end{frame}

\begin{frame}{Task sheet \#1}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture}(-2.46,-0.68)(4.84,4.04)
\psline(-1.62,1.18)(0.1,3.22)
\psline(0.1,3.22)(3.24,2.96)
\psline(3.24,2.96)(3.98,0.68)
\psline(3.98,0.68)(1.2,0.14)
\psline(1.2,0.14)(-1.62,1.18)
\psline(0.1,3.22)(1.2,0.14)
\psline(1.2,0.14)(3.24,2.96)
\rput[tl](-0.96,2.44){2}
\rput[tl](1.88,3.46){5}
\rput[tl](0.46,1.76){3}
\rput[tl](2.1,1.98){1}
\rput[tl](3.82,2.08){2}
\rput[tl](2.76,0.38){4}
\rput[tl](-0.42,0.6){6}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.1,3.22)
\rput[bl](-0.18,3.44){\qrqrqr{$A$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-1.62,1.18)
\rput[bl](-1.98,1.12){\qrqrqr{$B$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.24,2.96)
\rput[bl](3.42,3.1){\qrqrqr{$C$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](1.2,0.14)
\rput[bl](1.04,-0.22){\qrqrqr{$D$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.98,0.68)
\rput[bl](4.26,0.5){\qrqrqr{$E$}}
\end{pspicture}
\end{center}

\end{frame}

\begin{frame}{Task sheet \#1}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture}(2.26,-3.48)(11.48,4.1)
\psline(5.34,3.02)(6.94,0.32)
\psline(6.94,0.32)(10.08,0.35)
\psline(10.08,0.35)(8.48,3.05)
\psline(8.48,3.05)(8.54,-2.38)
\psline(5.4,-2.42)(8.54,-2.38)
\psline(3.8,0.28)(5.4,-2.42)
\psline(3.8,0.28)(8.48,3.05)
\psline(5.34,3.02)(5.4,-2.42)
\psline(10.08,0.35)(8.54,-2.38)
\psline(5.34,3.02)(8.48,3.05)
\rput[tl](4.58,1.24){8}
\rput[tl](4.38,-1.08){3}
\rput[tl](7.14,-2.52){5}
\rput[tl](5.6,0.42){2}
\rput[tl](6.64,1.2){3}
\rput[tl](7.08,3.44){2}
\rput[tl](9.32,2.2){3}
\rput[tl](7.52,0.28){5}
\rput[tl](8.62,1.76){2}
\rput[tl](9.52,-0.82){2}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.8,0.28)
\rput[bl](3.4,0.4){\qrqrqr{$A$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](5.4,-2.42)
\rput[bl](4.94,-2.74){\qrqrqr{$B$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](8.54,-2.38)
\rput[bl](8.76,-2.64){\qrqrqr{$C$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](10.08,0.35)
\rput[bl](10.16,0.56){\qrqrqr{$D$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](8.48,3.05)
\rput[bl](8.56,3.26){\qrqrqr{$E$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](5.34,3.02)
\rput[bl](5.42,3.22){\qrqrqr{$F$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.94,0.32)
\rput[bl](7.02,0.52){\qrqrqr{$G$}}
\end{pspicture}
\end{center}


\end{frame}

\begin{frame}{Task sheet \#1}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture}(-4.08,0.38)(4.86,8.54)
\psline(-2.59,5.55)(-0.52,5.2)
\psline(-0.52,5.2)(1.56,7.27)
\psline(-0.87,7.27)(1.2,5.2)
\psline(-0.87,7.27)(1.56,7.27)
\psline(3.28,5.55)(1.56,7.27)
\psline(1.2,5.2)(1.2,3.48)
\psline(1.2,3.48)(3.28,3.12)
\psline(3.28,5.55)(1.56,1.4)
\psline(1.2,5.2)(0.34,4.34)
\psline(-0.52,5.2)(0.34,4.34)
\psline(-0.52,3.48)(-0.52,5.2)
\psline(-2.59,3.12)(-0.87,1.4)
\psline(-0.87,1.4)(-0.52,3.48)
\psline(-2.59,3.12)(-0.52,3.48)
\psline(-2.59,5.55)(-0.52,3.48)
\psline(1.2,3.48)(-0.52,3.48)
\psline(-0.52,3.48)(1.56,1.4)
\psline(1.56,1.4)(3.28,3.12)
\psline(3.28,5.55)(3.28,3.12)
\rput[tl](0.28,2.42){4}
\rput[tl](-0.94,2.78){3}
\rput[tl](-2,2.42){5}
\rput[tl](2.62,2.42){3}
\rput[tl](1.7,2.6){5}
\rput[tl](-1.6,3.7){4}
\rput[tl](0.44,3.5){2}
\rput[tl](3.5,4.58){4}
\rput[tl](1.72,3.76){2}
\rput[tl](0.8,4.76){1}
\rput[tl](-0.26,4.84){2}
\rput[tl](-0.7,4.64){3}
\rput[tl](-1.88,4.62){5}
\rput[tl](1.3,4.58){3}
\rput[tl](2.62,6.72){4}
\rput[tl](1.04,6.64){5}
\rput[tl](-0.46,6.66){4}
\rput[tl](0.3,7.64){4}
\rput[tl](-1.5,5.76){3}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](1.56,1.4)
\rput[bl](1.7,1.1){\qrqrqr{$A$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.28,3.12)
\rput[bl](3.48,2.92){\qrqrqr{$B$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.28,5.55)
\rput[bl](3.54,5.44){\qrqrqr{$C$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](1.56,7.27)
\rput[bl](1.64,7.48){\qrqrqr{$D$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-0.87,7.27)
\rput[bl](-1.24,7.44){\qrqrqr{$E$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-2.59,5.55)
\rput[bl](-2.9,5.54){\qrqrqr{$F$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-2.59,3.12)
\rput[bl](-3.02,3.02){\qrqrqr{$G$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-0.87,1.4)
\rput[bl](-0.88,1.04){\qrqrqr{$H$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](1.2,5.2)
\rput[bl](1.46,5.16){\qrqrqr{$I$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-0.52,5.2)
\rput[bl](-0.6,5.4){\qrqrqr{$J$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](-0.52,3.48)
\rput[bl](-0.36,3.6){\qrqrqr{$K$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](1.2,3.48)
\rput[bl](1.36,3.58){\qrqrqr{$L$}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.34,4.34)
\rput[bl](0.28,4.52){\qrqrqr{$M$}}
\end{pspicture}
\end{center}




\end{frame}


\begin{frame}{Dijkstra's algorithm}

Vertex we are starting from : \emph{initial vertex}. 

\emph{Distance of a vertex Y} :  distance from the initial vertex to it. \pause

\begin{enumerate}
\item Assign to every vertex a distance value : $0$ for the initial vertex and $\infty$) for all other vertices.\pause
\item Mark all vertices as unvisited. Set initial vertex as current.\pause
\item For current node, consider all its unvisited neighbours and calculate their distance. If this distance is less
than the previously recorded distance, overwrite the distance.\pause
\item When all neighbours of the current node have been considered, mark it as visited. \pause
\item Set the unvisited vertex with the smallest distance (from the initial node) as the next \emph{current vertex} and
continue from step 3.
\end{enumerate}

\end{frame}

\begin{frame}{Dijkstra's algorithm : An example}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2,-2)(11,4)
\psline(3.22,3.02)(0.32,1.18)
\psline(0.32,1.18)(3.46,-0.48)
\psline(3.46,-0.48)(6.44,1.86)
\psline(6.44,1.86)(3.22,3.02)
\rput[tl](1.52,2.4){2}
\rput[tl](1.86,0.24){3}
\rput[tl](4.82,2.84){5}
\rput[tl](5.16,0.74){6}
\uput[l](0.32,1.18){A(0)}
\uput[u](3.22,3.02){B($\infty$)}
\uput[d](3.46,-0.48){C($\infty$)}
\uput[r](6.44,1.86){D($\infty$)}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.32,1.18)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.22,3.02)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.46,-0.48)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.44,1.86)
\end{pspicture*}
\end{center}

\end{frame}

\begin{frame}{Dijkstra's algorithm : An example}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2,-2)(11,4)
\psline(3.22,3.02)(0.32,1.18)
\psline(0.32,1.18)(3.46,-0.48)
\psline(3.46,-0.48)(6.44,1.86)
\psline(6.44,1.86)(3.22,3.02)
\rput[tl](1.52,2.4){2}
\rput[tl](1.86,0.24){3}
\rput[tl](4.82,2.84){5}
\rput[tl](5.16,0.74){6}
\uput[l](0.32,1.18){\textbf{A(0)}}
\uput[u](3.22,3.02){B(2)}
\uput[d](3.46,-0.48){C(3)}
\uput[r](6.44,1.86){D($\infty$)}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.32,1.18)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.22,3.02)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.46,-0.48)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.44,1.86)
\end{pspicture*}
\end{center}

\end{frame}

\begin{frame}{Dijkstra's algorithm : An example}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2,-2)(11,4)
\psline(3.22,3.02)(0.32,1.18)
\psline(0.32,1.18)(3.46,-0.48)
\psline(3.46,-0.48)(6.44,1.86)
\psline(6.44,1.86)(3.22,3.02)
\rput[tl](1.52,2.4){2}
\rput[tl](1.86,0.24){3}
\rput[tl](4.82,2.84){5}
\rput[tl](5.16,0.74){6}
\uput[l](0.32,1.18){\textbf{A(0)}}
\uput[u](3.22,3.02){\textbf{B(2)}}
\uput[d](3.46,-0.48){C(3)}
\uput[r](6.44,1.86){D(7)}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.32,1.18)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.22,3.02)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.46,-0.48)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.44,1.86)
\end{pspicture*}
\end{center}

\end{frame}

\begin{frame}{Dijkstra's algorithm : An example}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1cm,yunit=1cm,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-2,-2)(11,4)
\psline(3.22,3.02)(0.32,1.18)
\psline(0.32,1.18)(3.46,-0.48)
\psline(3.46,-0.48)(6.44,1.86)
\psline(6.44,1.86)(3.22,3.02)
\rput[tl](1.52,2.4){2}
\rput[tl](1.86,0.24){3}
\rput[tl](4.82,2.84){5}
\rput[tl](5.16,0.74){6}
\uput[l](0.32,1.18){\textbf{A(0)}}
\uput[u](3.22,3.02){\textbf{B(2)}}
\uput[d](3.46,-0.48){\textbf{C(3)}}
\uput[r](6.44,1.86){\textbf{D(7)}}
\psdots[dotsize=5pt 0,linecolor=qrqrqr](0.32,1.18)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.22,3.02)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](3.46,-0.48)
\psdots[dotsize=5pt 0,linecolor=qrqrqr](6.44,1.86)
\end{pspicture*}
\end{center}

\end{frame}

\begin{frame}{Task sheet \#2}

\begin{center}
\includegraphics[angle=90,width=10cm]{s02e22/manhattan.eps}
\end{center}

\end{frame}

\begin{frame}{Task sheet \#3}

\begin{center}
\includegraphics[width=10cm]{s02e22/englandmap.eps}
\end{center}

\end{frame}

\begin{frame}[containsverbatim]{Dijkstra's algorithm in pseudo-code}

{\footnotesize

\begin{verbatim}
 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph: // Initializations
 3          dist[v] := infinity     
        // Unknown distance function from source to v
 4          previous[v] := undefined
        // Previous node in optimal path from source
 5      dist[source] := 0           
        // Distance from source to source
 6      Q := the set of all nodes in Graph
        // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:       // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
10              break               
        // all remaining vertices are inaccessible
11          remove u from Q
12          for each neighbor v of u:
        // where v has not yet been removed from Q.
13              alt := dist[u] + dist_between(u, v) 
14              if alt < dist[v]:    // Relax (u,v,a)
15                  dist[v] := alt
16                  previous[v] := u
17      return previous[]
\end{verbatim}
}

\end{frame}



\end{document}
