% -*-coding: iso-8859-1  -*- 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
%\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc} 
\usepackage{ae} 
\usepackage[ansinew]{inputenc} 
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{color}
%\usepackage[lmargin=2cm, rmargin=2cm, tmargin=2cm, bmargin=2cm]{geometry}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage[round]{natbib}
\usepackage{amsthm}
\usepackage{setspace}
\usepackage{url}

\usepackage[british,english]{babel}

\usepackage{algorithm2e}
\input{algorithm2e-pt}
\input{sourcecode}

\usepackage{anysize}
\marginsize{3cm}{2cm}{2cm}{2cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\thispagestyle{empty}

\onehalfspacing

{ \Large \centering \textbf{MO405 - Teoria dos grafos} \\ }
{ \Large \centering \textbf{Algoritmo de Dijkstra para encontrar caminhos mínimos} \\ }
{ \Large \centering \textbf{Lucas de Oliveira} \\ }
{ \Large \centering \textbf{30 - Março - 2012} \\ }

\vspace{1cm}

Considere a situação onde temos um grafo $G$=($V$,$E$) sendo $V$ e
$E$, respectivamente, o conjunto de vértices e arestas do grafo. Além
disso, também temos pesos atribuídos às arestas do grafo pela função
$peso$ : $E \rightarrow \mathbb{R}_+$. Neste contexto, queremos
encontrar caminhos mínimos, em termos dos pesos das arestas, que vão
de $v$ até os demais vértices do grafo. O algoritmo abaixo apresenta
uma solução para este problema desenvolvida por Edsger Dijkstra em
1956. No algoritmo considere que o conjunto $V$ seja formado pelos
números inteiros no intervalo [1,$n$] onde $n$ é o total de vértices
no conjunto. Denotamos o conjunto dos vértices adjacentes ao vértice
$v$ por $N$($v$). É importante ressaltar também que utilizamos uma
fila de prioridade $f$ que possui os métodos \emph{insere},
\emph{decrescePrioridade}, \emph{tamanho} e \emph{retiraMínimo}. O
nome de cada método esclarece a operação realizada por ele, sendo que
nos métodos \emph{insere} e \emph{descrecePrioridade} são fornecidos
dois parâmetros que são o vértice e sua (nova) prioridade na fila,
respectivamente.

\vspace{15pt}

\begin{algorithm}[H]
\SetAlgoLined
\Entrada{Um grafo $G$ e um vértice $v$.}
\Saida{Um vetor $d$ de distâncias mínimas de $v$ para os demais vértices, e um vetor $p$ representando uma árvore de caminhos mínimos de $v$ até os demais vértices.}
\textbf{Vetor}  $d$[$1$..$n$], $p$[$1$..$n$]\;
\textbf{FilaPrioridade}  $f$\;
\Para{$i \leftarrow 1$ \Ate n}{
	$d[i] \leftarrow \infty$\;
}
$d[v] \leftarrow 0$\;
$f$.\textit{insere}($v$, $d[v]$)\;
\Enqto{$f$.\textit{tamanho}() $>$ 0}{
	$u \leftarrow f$.\textit{mínimo}()\;
	\ParaCada{$w \in N$($u$)}{
		\Se{$d[w] > d[u]$ + \textit{peso}($uw$)}{
                        \Se{$d[w] = \infty$}{
                                $f$.\textit{insere}($w$, $d[w]$)\;
                        }
			$d[w] \leftarrow d[u]$ + \textit{peso}($uw$)\;
			$p[w] \leftarrow u$\;
			$f$.\textit{decresce}($w$, $d[w]$)\;
		}
	}
}
\caption{Algoritmo de Dijkstra para encontrar caminhos mínimos.}
\label{Alg:dijkstra}
\end{algorithm}

\vspace{15pt}

Nos anexos é apresentada uma implementação deste algoritmo feita na linguagem Java pela aluna Juliana M. Destro.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{plainnat}
%\bibliographystyle{unsrtnat}
%\bibliographystyle{abbrvnat}
%\bibliography{refs}

\end{document}
