PESQUISA OPERACIONAL

Disciplina: Teoria dos Grafos

BUSCA EM GRAFOS

CAPÍTULO 6 - Um Exemplo Prático de Aplicação do Algoritmo de DIJKSTRA

 

Professor: Altamir A. R. Araldi

Apostila de um Curso de Mestrado! 

  

Curso Completo (Apostila)

 

 

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.

EXEMPLO DO ALGORITMO DE DIJSTRA

1a ITERAÇÃO:

    p=x1

    Γ(x1)={x1, x7, x9, x8}

    l(x2)=min. [∞, 0+10]=10

    l(x7)=min. [∞, 0+3]  = 3

    l(x8)=min. [∞, 0+6]  = 6

    l(x9)=min. [∞, 0+12]=12

 

    xi*=x7, pois l(x7)=min.(l(xi)=3

    p=x7

 

2a ITERAÇÃO:

   Γ(x7)={x2, x4, x6, x9}

   l(x2)=min. [10, 3+2]  =  5

   l(x4)=min. [∞, 3+4]  =  7

   l(x9)=min. [12, 3+24]=12

 

   p=x2

 

 

Valores dos labels

  A partir de 11 Set de 2020

Você é o Visitante de Número

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos