\documentclass[11pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage{isabelle,isabellesym}
\usepackage{xspace}

% further packages required for unusual symbols (see also
% isabellesym.sty), use only when needed

\usepackage{amssymb}
  %for \<leadsto>, \<box>, \<diamond>, \<sqsupset>, \<mho>, \<Join>,
  %\<lhd>, \<lesssim>, \<greatersim>, \<lessapprox>, \<greaterapprox>,
  %\<triangleq>, \<yen>, \<lozenge>

% this should be the last package used
\usepackage{pdfsetup}

% urls in roman style, theory text in math-similar italics
\urlstyle{rm}
\isabellestyle{it}

% for uniform font size
\renewcommand{\isastyle}{\isastyleminor}

\renewcommand{\isamarkupchapter}[1]{\section{#1}}
\renewcommand{\isamarkupsection}[1]{\subsection{#1}}
\renewcommand{\isamarkupsubsection}[1]{\subsubsection{#1}}
\renewcommand{\isamarkupsubsubsection}[1]{\paragraph{#1}}

\newcommand{\fw}{Floyd-Warshall algorithm\xspace}

\begin{document}

\title{The Floyd-Warshall Algorithm for Shortest Paths}
\author{Simon Wimmer and Peter Lammich}

\maketitle
\begin{abstract}
  The \fw \cite{floyd, roy, warshall} is a classic dynamic programming algorithm to compute
  the length of all shortest paths between any two vertices in a graph
  (i.e. to solve the all-pairs shortest path problem, or \textit{APSP} for short).
  Given a representation of the graph as a matrix of weights $M$, it computes another matrix $M'$
  which represents a graph with the same path lengths and contains the length of the shortest path
  between any two vertices $i$ and $j$.
  This is only possible if the graph does not contain any negative cycles. However, in this case the \fw will detect the situation by
  calculating a negative diagonal entry.
  This entry includes a formalization of the algorithm and of these key properties.
  The algorithm is refined to an efficient imperative version using the Imperative Refinement Framework.
\end{abstract}

\setcounter{tocdepth}{2}
\tableofcontents
\newpage

% sane default for proof documents
\parindent 0pt\parskip 0.5ex

% generated text of all theories
\input{session}

% optional bibliography
\bibliographystyle{alpha}
\bibliography{root}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
