Projeto e Análise de Algoritmos I

Aula 17 - Distância em Grafos Valorados: Algoritmo de Dijkstra

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Caminho Mínimo com Origem Única

Problema do Caminho Mínimo com Origem Única

Caminho Mínimo com Origem Única

Problema do Caminho Mínimo com Origem Única

Entrada:

  • Um grafo direcionado G=(V,E)
    • Cada arco tem um custo não negativo l_e para e\in E.
  • Vértice de origem s.

Saída: Para cada v\in V:

  • L(v)= custo do menor caminho entre s-v em G (distância).

Importante:

  • l_e \geq 0, \forall e\in E.
  • Assumiremos representação por lista de adjacência.

Caminho Mínimo com Origem Única

P. Custo do caminho 0-6? 25.

P. Custo do caminho 0-7? 8.

Caminho Mínimo com Origem Única

Algoritmo ingênuo: calcula todos os caminhos e seus respectivos pesos totais, buscando o menor peso total.

Quantos caminhos entre dois nodos específicos num K_n?

\boxed{\displaystyle \sum_{k=0}^{n-2} \binom{n-2}{k} k! = \sum_{k=0}^{n-2}\frac{(n-2)!}{(n-2-k)!} = (n-2)! \sum_{i=0}^{n-2} \frac{1}{i!} \;\approx\; e \cdot (n - 2)!}

Problema do Caminho Mínimo com Origem Única

Como visto anteriormente para grafos não valorados:

\begin{algorithmic} \Procedure{BuscaLargura}{$G=(V,E), s$} \State \textbf{Entrada:} Um grafo $G=(V,E)$ e um vértice inicial $s$ \State \textbf{Saída:} Distâncias $d[v]$ de $s$ até cada $v \in V$ \State Inicialize $d[v] \gets \infty$ para todo $v \in V$ \State $d[s] \gets 0$ \State $Q \gets \{s\}$ \Comment{Fila (FIFO) inicializada com $s$} \While{$Q \neq \emptyset$} \State $v \gets Q.pop()$ \For{$(v,w) \in E$} \If{$d[w] = \infty$} \State $d[w] \gets d[v] + 1$ \State Adiciona $w$ a $Q$ \EndIf \EndFor \EndWhile \EndProcedure \end{algorithmic}

Custo: O(m+n).

Problema do Caminho Mínimo com Origem Única

Entrada: um grafo G=(V,E) com m=|E| e n=|V|:

  • Cada arco tem um custo não negativo l_e para e\in E.


P. É possível usar Busca em Largura?

Ideia: substituir todo arco por arcos de tamanho 1 e usar BFS.

3 1 1 1 S T S v w T ⟹

R. O grafo pode crescer muito, e.g., peso 10^{10}.

Algoritmo de Dijkstra (1959)

Algoritmo de Dijkstra: Exemplo

Exemplo:

Entrada: o grafo G abaixo, com pesos l_e \geq 0 nas arestas, e o vértice de origem s = S (em azul).

1 3 5 4 4 1 2 6 S A B D C E F

Saída: para cada v \in V, a distância d(S,v) do menor caminho de S até v (caminho entre parênteses):

  • d(S,S)=\ 0 \quad (S)
  • d(S,A)=\ 1 \quad (SA)
  • d(S,B)=\ 3 \quad (SB)
  • d(S,C)=\ 4 \quad (SBC)
  • d(S,D)=\ 6 \quad (SAD)
  • d(S,E)=\ 8 \quad (SADE)
  • d(S,F)=\ \infty

Algoritmo de Dijkstra: Pseudocódigo

\begin{algorithmic} \Procedure{Dijkstra}{$G=(V,E,w), s$} \State \textbf{Entrada:} Um grafo com pesos não-negativos $(V, E, w)$ e um nodo $s \in V$ \State \textbf{Saída:} Uma tabela $\text{dist}$ associando cada $v \in V$ à sua distância $d(s,v)$ \State // Inicialização \State $X \gets \{s\}$ \State $\text{dist}(s) \gets 0$ \State $\text{dist}(v) \gets +\infty$ para todo $v \neq s$ \State // Laço principal \While{existe uma aresta $(v, w)$ tal que $v \in X$ e $w \notin X$} \State $(v^*, w^*) \gets$ tal aresta que minimiza $\text{dist}(v) + \ell_{vw}$ \State Adicione $w^*$ a $X$ \State $\text{dist}(w^*) \gets \text{dist}(v^*) + \ell_{v^*w^*}$ \EndWhile \State \textbf{Retorne} $\text{dist}$ \EndProcedure \end{algorithmic}

Algoritmo de Dijkstra

processados ainda não processados X V − X fronteira s candidatas para (v*, w*) de V − X para X: não é candidata

Algoritmo de Dijkstra: Execução

1 3 5 4 4 1 2 6 S A B D C E F


\begin{array}{|ll|} \hline \mathbf{dist_0} & \\ \color{blue}S & \color{blue}0 \\ A & 1 \\ B & 3 \\ C & \infty \\ D & \infty \\ E & \infty \\ F & \infty \\ \hline \color{blue}\mathbf{X_0} & \\ \color{blue}\{S\} & \\ \hline \color{red}\text{min:} & A \\ \hline \end{array}

\begin{array}{|ll|} \hline \mathbf{dist_1} & \\ \color{blue}S & \color{blue}0 \\ \color{blue}A & \color{blue}1 \\ B & 3 \\ C & 5 \\ D & 6 \\ E & \infty \\ F & \infty \\ \hline \color{blue}\mathbf{X_1} & \\ \color{blue}\{S,A\} & \\ \hline \color{red}\text{min:} & B \\ \hline \end{array}

\begin{array}{|ll|} \hline \mathbf{dist_2} & \\ \color{blue}S & \color{blue}0 \\ \color{blue}A & \color{blue}1 \\ \color{blue}B & \color{blue}3 \\ C & 4 \\ D & 6 \\ E & \infty \\ F & \infty \\ \hline \color{blue}\mathbf{X_2} & \\ \color{blue}\{S,A,B\} & \\ \hline \color{red}\text{min:} & C \\ \hline \end{array}

\begin{array}{|ll|} \hline \mathbf{dist_3} & \\ \color{blue}S & \color{blue}0 \\ \color{blue}A & \color{blue}1 \\ \color{blue}B & \color{blue}3 \\ \color{blue}C & \color{blue}4 \\ D & 6 \\ E & 10 \\ F & \infty \\ \hline \color{blue}\mathbf{X_3} & \\ \color{blue}\{S,A,B,C\} & \\ \hline \color{red}\text{min:} & D \\ \hline \end{array}

\begin{array}{|ll|} \hline \mathbf{dist_4} & \\ \color{blue}S & \color{blue}0 \\ \color{blue}A & \color{blue}1 \\ \color{blue}B & \color{blue}3 \\ \color{blue}C & \color{blue}4 \\ \color{blue}D & \color{blue}6 \\ E & 10 \\ F & \infty \\ \hline \color{blue}\mathbf{X_4} & \\ \color{blue}\{S,A,B,C,D\} & \\ \hline \color{red}\text{min:} & E \\ \hline \end{array}

\begin{array}{|ll|} \hline \mathbf{dist_5} & \\ \color{blue}S & \color{blue}0 \\ \color{blue}A & \color{blue}1 \\ \color{blue}B & \color{blue}3 \\ \color{blue}C & \color{blue}4 \\ \color{blue}D & \color{blue}6 \\ \color{blue}E & \color{blue}8 \\ F & \infty \\ \hline \color{blue}\mathbf{X_5} & \\ \color{blue}\{S,A,B,C,D,E\} & \\ \hline \color{red}\text{para!} & \\ \hline \end{array}

Visualização do Algoritmo de Dijkstra

lucasalegre.github.io/dijkstra-visualizer

Algoritmo de Dijkstra: Limitações

  • Uma restrição importante ao algoritmo de Dijkstra é o fato de que os grafos necessariamente precisam possuir pesos não-negativos.


Exemplo:

G1 8 2 −2 2 2 A B C D E F G2 8 2 4 −5 2 A B C D E F G3 8 2 −30 10 2 A B C D E F

Responda:

  • Qual a distância entre A e F?
  • O que o algoritmo de Dijkstra apontaria como menor distância se fosse aplicado?
  • Por que o algoritmo de Dijkstra não funciona em alguns desses grafos?

Algoritmo de Dijkstra: Limitações

P. Como reduzir o problema do caminho mínimo com custos negativos para o mesmo problema com custos não negativos?

1 −5 −2 S V T
  • Ideia: Adiciona uma constante grande aos arcos.
6 0 3 S V T

Observação 1. Não preserva os caminhos mínimos.

Observação 2. Dijkstra também não funciona no exemplo.

Algoritmo de Dijkstra: Limitações

Corretude do Algoritmo de Dijkstra

Corretude do Algoritmo de Dijkstra

Teorema. Para todo grafo direcionado com arcos de custos não negativos, o algoritmo de Dijkstra computa todos os caminhos mínimos à partir da origem.

d[v]=L(v), \forall v\in V, onde:

  • d[v] o que o algoritmo computa.
  • L(v) o real menor caminho de s até v.


Prova. Por indução no número de iterações do algoritmo.

Corretude: Caso Base e Hipótese

Invariante. Ao fim de cada iteração, d[v] = L(v) para todo v \in X.

Caso base. Antes do laço, X = \{s\} e d[s] = 0 = L(s) (pesos \geq 0).

Hipótese de indução (HI). No início da iteração, d[v] = L(v) \forall v \in X.


Iteração atual. O algoritmo escolhe o arco da fronteira (\textcolor{#3a7a10}{v^*}, \textcolor{#3a7a10}{w^*}) que minimiza d[v] + \ell_{vw} e faz d[\textcolor{#3a7a10}{w^*}] = d[\textcolor{#3a7a10}{v^*}] + \ell_{\textcolor{#3a7a10}{v^*}\textcolor{#3a7a10}{w^*}}.

X ℓv*w* s v* w* caminho mínimo de s a v*: custo L(v*) = d[v*] (HI) caminho P* de s a w*: custo d[v*] + ℓv*w* = d[w*]

Como \textcolor{#3a7a10}{P^*} é um caminho de custo d[\textcolor{#3a7a10}{w^*}], já sabemos que L(\textcolor{#3a7a10}{w^*}) \leq d[\textcolor{#3a7a10}{w^*}].

Falta mostrar: nenhum caminho de s a \textcolor{#3a7a10}{w^*} custa menos que d[\textcolor{#3a7a10}{w^*}].

Corretude: Passo de Indução

Por contradição. Suponha que existe um caminho \textcolor{#d9690b}{P} de s a \textcolor{#3a7a10}{w^*} com \text{custo}(\textcolor{#d9690b}{P}) < d[\textcolor{#3a7a10}{w^*}].

  • Como \textcolor{#d9690b}{P} sai de s \in X e chega em \textcolor{#3a7a10}{w^*} \notin X, ele cruza a fronteira.
  • Seja (\textcolor{#d9690b}{y}, \textcolor{#d9690b}{z}) o primeiro arco de \textcolor{#d9690b}{P} com \textcolor{#d9690b}{y} \in X e \textcolor{#d9690b}{z} \notin X:
X V − X ℓv*w* custo ≥ L(y) ℓyz custo ≥ 0 s v* y z w* P* (algoritmo): custo d[w*] P (hipotético): custo < d[w*]
\text{custo}(\textcolor{#d9690b}{P})\geq L(\textcolor{#d9690b}{y}) + \ell_{\textcolor{#d9690b}{y}\textcolor{#d9690b}{z}} + 0(definição de L e pesos \geq 0)
= d[\textcolor{#d9690b}{y}] + \ell_{\textcolor{#d9690b}{y}\textcolor{#d9690b}{z}}(HI, pois \textcolor{#d9690b}{y} \in X)
\geq d[\textcolor{#3a7a10}{v^*}] + \ell_{\textcolor{#3a7a10}{v^*}\textcolor{#3a7a10}{w^*}}((\textcolor{#d9690b}{y}, \textcolor{#d9690b}{z}) é arco da fronteira e (\textcolor{#3a7a10}{v^*}, \textcolor{#3a7a10}{w^*}) é o mínimo)
= d[\textcolor{#3a7a10}{w^*}](definição de d[\textcolor{#3a7a10}{w^*}] no algoritmo)

Contradição! Então nenhum caminho é mais curto: d[\textcolor{#3a7a10}{w^*}] = L(\textcolor{#3a7a10}{w^*}) e o invariante vale para X \cup \{\textcolor{#3a7a10}{w^*}\}.

Corretude: Conclusão

Término. Cada iteração adiciona um vértice a X, então o laço executa no máximo n - 1 vezes.

Ao final, pelo invariante, d[v] = L(v) para todo v \in X. E os vértices fora de X?

  • Se X = V, não sobrou nenhum vértice.
  • Se X \neq V, o laço parou porque nenhum arco sai de X. Todo caminho de s até v \notin X teria que cruzar a fronteira, então v é inalcançável: L(v) = +\infty = d[v].
X V − X d = L (invariante) d = L = +∞ nenhum arco sai de X s

Conclusão. d[v] = L(v) para todo v \in V: o algoritmo de Dijkstra computa todas as distâncias mínimas a partir de s. \blacksquare

Análise do Algoritmo de Dijkstra

Análise do Algoritmo de Dijkstra

\begin{algorithmic} \Procedure{Dijkstra}{$G=(V,E,w), s$} \State \textbf{Entrada:} Um grafo com pesos não-negativos $(V, E, w)$ e um nodo $s \in V$ \State \textbf{Saída:} Uma tabela $\text{dist}$ associando cada $v \in V$ à sua distância $d(s,v)$ \State // Inicialização \State $X \gets \{s\}$ \State $\text{dist}(s) \gets 0$ \State $\text{dist}(v) \gets +\infty$ para todo $v \neq s$ \State // Laço principal \While{existe uma aresta $(v, w)$ tal que $v \in X$ e $w \notin X$} \State $(v^*, w^*) \gets$ tal aresta que minimiza $\text{dist}(v) + \ell_{vw}$ \State Adicione $w^*$ a $X$ \State $\text{dist}(w^*) \gets \text{dist}(v^*) + \ell_{v^*w^*}$ \EndWhile \State \textbf{Retorne} $\text{dist}$ \EndProcedure \end{algorithmic}

P. Qual o tempo de execução?

Análise do Algoritmo de Dijkstra

Ideia Principal

Uma implementação direta mantém, para cada vértice, uma variável booleana indicando se ele pertence ao conjunto X.

A cada iteração:

  • Percorrem-se todas as arestas (v, w), com v \in X e w \notin X;
  • Calcula-se o valor de Dijkstra \text{dist}(v) + \ell_{vw} em tempo constante por aresta;
  • Escolhe-se a aresta com o menor valor e adiciona-se seu vértice destino a X.

Análise de Complexidade

São no máximo n - 1 iterações, cada uma percorrendo m arestas: T(n, m) = \mathcal{O}(n) \times \mathcal{O}(m) = \mathcal{O}(mn)

Análise de Complexidade

Python 3.12.3, Ubuntu 24.04.2 LTS, Intel® Core™ i7-4810MQ × 8

Naive Dijkstra em Python

Naive Dijkstra em Python

Além do Algoritmo de Dijkstra

Edsger W. Dijkstra

  • Prêmio Turing em 1972.
  • Primeira implementação de ALGOL 60.
  • Programação Estruturada (“Go To statement considered harmful” (1968)).
  • Semáforos para controle de múltiplos processos, \dots


“In their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind.”

Além de Dijkstra

  • Algoritmo de Bellman-Ford: resolve o problema para grafos com um vértice de origem e arestas que podem ter pesos negativos.

    • \mathcal{O}(mn)

  • Algoritmo de Floyd-Warshall: determina a distância entre todos os pares de vértices de um grafo com arestas que podem ter pesos negativos (mas não ciclo negativos).

    • \mathcal{O}(n^2)

  • Algoritmo de Johnson: determina a distância entre todos os pares de vértices de um grafo em grafos esparsos. Pode haver arestas negativas, mas não ciclos negativos.

    • \mathcal{O}(n^2 \log n + mn)

  • Caminhos mínimos em DAGs: grafo acíclico dirigido.’’

  • Algoritmo A^*: um algoritmo de busca heurística que calcula o caminho mínimo com um vértice de origem.

    • \mathcal{O}(m \log n)

Próxima Aula

  • Vimos uma versão ingênua do algoritmo de Dijkstra, com complexidade \mathcal{O}(mn).
  • Na próxima aula, veremos uma versão mais eficiente do algoritmo de Dijkstra, com complexidade \mathcal{O}(m \log n), filas de prioridade (heaps).

?