Exemplo de Aplicação do Algoritmo de DIJSTRA.

 

1. NOME: Algoritmo de Dijstra

    OBJETIVO: Determinar o Caminho de Mínimo Custo entre dois Vértices específicos do Grafo.

 

2. AUTOR: Dijstra

    DATA:

 

3. NOMENCLATURA:

    T     – árvore

    G     – grafo

    s     – ponto inicial

    t     – ponto final

    xi    – vértices pertencentes a G

    l(xi) – custo de uma árvore

 

DEFINIÇÕES, FUNDAMENTOS E DESCRIÇÃO DO MÉTODO:

É baseado na designação de labels temporários aos vértices. Sendo o label do vértice um limite superior no comprimento do caminho desde s até aquele vértice. Estes labels são continuamente reduzidos por um procedimento iterativo e com cada iteração, exatamente um dos labels temporários se torna permanente. Isto indica que não é mais um limite superior, senão o comprimento exato do caminho mais curto desde s até aquele vértice.

 

4. ALGORITMO CONCEITUAL

INICIALIZAÇÃO:

Passo 1: - l(s)=0 e permanente 

               l(xi)=∞ para xi ≠ s e temporário

            - p=s

 

ATUALIZAÇÃO DOS LABELS

Passo 2: - para xi ∈ Γ(p), l(xi)=min. [l(xi), l(p) + C(p,xi)]

 

DETERMINAÇÃO DOS LABELS PERMANENTES

Passo 3: - determinar xi*, sendo l(xi*)=min. [l(xi)]

 

Passo 4: - p=xi*

 

Passo 5:

   Se é desejado o caminho de s para t:

      - p=t, está determinado o caminho de mínimo custo, FIM.

      - p ≠ t, voltar ao Passo 2.

   Se o caminho de s para todos os vértices é desejado:

      - todos os vértices têm labels permanentes, FIM.

      - alguns labels são temporários, voltar ao Passo 2.

 

5. OBSERVAÇÕES RELEVANTES

É o algoritmo mais eficiente para solução do Problema de Caminho mais Curto entre s e t para Cij > 0 (Custo Positivo).

 

6.APLICAÇÕES:

Em Problemas de Transportes (Problemas de Minimizar Distâncias).

 

7.OUTROS ALGORITMOS DO GÊNERO

• Algoritmo do Caminho mais Confiável o qual considera a Probabilidade dos Custos;

• Algoritmo do caminho de Capacidade Máxima;

• Algoritmo do caminho de Capacidade Máxima Esperada;

• Algoritmo para achar k Caminhos mais Curtos entre Vértices;

• Algoritmo de PET/COM para achar o Tempo Mínimo de Terminar um Projeto.