\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}


\begin{document}

\module{The shortest path problem}{2}{22}{2 periods}

\prereq{Vocabulary and basic concepts of graph theory.}

\object{\begin{itemize}
        \item Understand the shortest path problem and its applications.
	\item Apply Dijkstra's algorithm. 
	\end{itemize}}

\mater{\begin{itemize}
	\item Task sheet \#1 : Easy graphs.
	\item Task sheet \#2 : More difficult graphs.
	\item Task shett \#3 : From Dover to Oxford.
	\item Beamer.
	\item Lesson.
	\end{itemize}}

\modpart{Introduction to the problem (task sheet \#1)}{1 period}

Weighted graphs and the shortest path problem is introduced in relation with the route planning websites and GPS
devices.

Students have to solve a few simple examples. Solutions are compared between students.

\modpart{Dijkstra's algorithm (task sheets \#1 and \#2)}{1 period}

Dijkstra's algorithm is introduced and applied on the simple graphs of part 1. Then, students have to apply it on a map
of Manhattan.

\modpart{From Dover to Oxford (task sheet \#3)}{1 period}

In the computer room, students use the Via Michelin website (http://www.viamichelin.co.uk/) to fill out two maps, one
with the distances between some cities, the other with the travelling times.

Then they have to use Dijskstra's algorithm to find the shortest and quickest routes between Dover and Oxford.

Finally, they compare the quickest and shortest itineraries they found with the ones given by the website.


\pagebreak

\moddocdis{The shortest path problem}{2}{22}{Task sheet \#1}

Find the shortest distance and shortest path from the vertex A to all the other vertices in the following graphs.

\begin{center}
\begin{tabular}{cc}
\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*}
&
\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{tabular}

\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=1.5cm,yunit=1.5cm,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}


% \pagebreak
% 
% \moddocdis{The shortest path problem}{2}{22}{Task sheet \#2}
% 
% 
% Below is a map of our school and the corresponding graph, with the main buildings or intersections as vertices and the
%walkways as edges. To simplifly the exercise, we consider that walking by a building is sometimes equivalent to walking
%through it, and that walking on the grass out of an existing walkway is forbidden. For example, it's impossible to go
%from building I to building S without passing through building G, or from L to intersection C2 without passing
%through~G. Also, we say it's impossible to walk from building L to building S from the inside.
% 
% \begin{center}
% \includegraphics[width=16cm]{s02e22/planlycee.eps}
% \end{center}
% 
% \begin{enumerate}
% \item Walk around the school to weight the edges of the graph with the approximative walking distances in secondes.
% \item Use Dijkstra's algorithm to find the shortest paths from entrance E1 to each building. Do the same from entrance
%E2.
% \item Decide what entrance you should use depending on your first lesson.
% %\item Find out what path you should follow from any building in the school to go to the refectory as quickly as
% possible.
% \end{enumerate}
% 

\pagebreak

\moddocdis{The shortest path problem}{2}{22}{Task sheet \#2}

Below is a subway map of Manhattan.

\begin{multicols}{2}
\begin{enumerate}
\item Chelsea International Hostel.
\item Battery Park.
\item Times Square.
\item The Empire State Building
\item Columbus Circle.
\item City Hall.
\item Brooklin Bridge.
\item Museum of Modern Art
\end{enumerate}
\end{multicols}

First, use the internet to find the closest subway station to each of these locations. Then, use the
subway map as a graph to find the shortest route between Union Square and each location. To do so, we will consider that
the average time between two subway stations is 5 minutes, and we will not take into account the possible
switches from one line to another, except 
\begin{itemize}
 \item 14 St 1239 to 6 Av L ;
 \item Port Authority ACE to Times Square 42 St ;
 \item Chambers St to Park Place ;
\end{itemize}
which will be accounted for  5 minutes each.

\bigskip

\begin{center}
\includegraphics[height=13cm]{s02e22/s02e22-subway.eps}
\end{center}




\pagebreak

\moddocdis{The shortest path problem}{2}{22}{Task sheet \#3}

Below are two maps of the South-East of England. We want to plan a trip from Dover to Oxford. We will do so in two
different ways, that's why there are two copies of the map.

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

\bigskip

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

\pagebreak

\begin{enumerate}
\item Use the route planning websites {\tt http://maps.google.co.uk/} or\\ {\tt http://www.viamichelin.co.uk/} to find
the distances and travel times for all adjacent towns on the map. Make sure that no itinerary passes through one other
town. For example, from Ashford to Royal Tunbridge Wells, the website may advise you to drive around Maidstone on the
M20 but you should take the distance and time along the direct route starting on the A28. Write down the distances on
one map and the travel times on the other.
\item Use Dijkstra's algorithm to find the shortest route between Dover and Oxford.
\item Use Dijkstra's algorithm to find the quickest route between Dover and Oxford.
\item Is the shortest route also the quickest ? Explain why it is so.
\item Compare the itineraries you found with the ones given by the route planning website. Explain any difference you
may notice.
\end{enumerate}



\pagebreak

\moddocdis{The shortest path problem}{2}{22}{Lesson}


\subsection*{Weighted graphs and the shortest path problem}

\begin{multicols}{2}

\defi{}{A \emph{weighted} graph is a graph where a real number, a \emph{weight} is assigned to each edge. The weight, or
length, of a path on this graph is the sum of the weights of its constituent edges.}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,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{multicols}


The \emph{shortest path problem} is the problem of finding a path between two vertices such that the sum of the weights
of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a
road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by
the distance or the time needed to travel that segment.

Different algorithms have been devised to solve this problem. One of the best known is \emph{Dijkstra's algorithm}, named after the Dutch computer scientist that conceived it in 1959. 

\subsection*{Dijkstra's algorithm}

Let's call the vertex we are starting from the \emph{initial vertex}. Let the \emph{distance of a vertex Y} be the
distance from the initial vertex to it. Dijkstra's algorithm will assign some initial distance values and will try to
improve them step-by-step.

\begin{enumerate}
\item Assign to every vertex a distance value. Set it to zero for our initial vertex and to infinity ($\infty$) for all other vertices (written in paper pen, as it will change when the algorithm is applied).
\item Mark all vertices as unvisited. Set initial vertex as current.
\item For current node, consider all its unvisited neighbours and calculate their distance (from the initial node). For example, if current vertex (A) has distance of 6, and an edge connecting it with another vertex (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
\item When all neighbours of the current node have been considered, mark it as visited, by circling its distance in green, for example. A visited vertex will not be checked ever again; its distance recorded now is final and minimal.
\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}

\newpage

\subsection*{Example}

\begin{multicols}{2}
The algorithm begins by initializing any vertex in the graph (vertex A, for example) a permanent label with the value of
0, and all other vertices a temporary label with the value of $\infty$. Visited vertices are typeset in bold.

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,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{multicols}

\begin{multicols}{2}
We then pick the non-visited vertex with the lowest label (vertex A in our example), and study all its neighbours. Whenever the distance from one of these neighbours through the current vertex is less then its temporary label, we change the label to this value. Once all neighbours have been visited, the current vertex is marked as visited.

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,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(0)}
\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{multicols}

We now apply the same process to vertex B, then to C and D. Notice that nothing is changed when studying C, as the distance from D is greater through C then it is through B. Also, there is nothing to do for vertex D.

\begin{multicols}{2}
\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,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}

\begin{center}
\newrgbcolor{qrqrqr}{0 0 0}
\psset{xunit=0.75cm,yunit=0.75cm,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{multicols}

The permanent labels of the vertices give the shortest distance from the vertex A.



\pagebreak

\moddocdis{The shortest path problem}{III}{1 -- Graphs continued}{01}{Algorithm}

{\small

\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{document}
