rfhdfjg

ATPS: Algoritmos e Estrutura de Dados

Centro Universitário Anhanguera
Uniabc

Curso: T.I
Turma: Noturno
Disciplina: Algoritmos e Estrutura de Dados

Santo André
2014

Desafio

Do nó A, para B, gasta 10 milissegundos no total da transmissão.
Melhor caminho: A -> B.

Do nó A, para C, gasta 10 milissegundos no total da transmissão.
Melhor caminho: A -> C.

Do nó A, para D, gasta 11 milissegundos no total da transmissão.
Melhor caminho: A -> D.

Do nó A, para E, gasta 19 milissegundos no total da transmissão.
Melhor caminho: A -> B -> E.

Do nó A, para F, gasta 18 milissegundos no total da transmissão.
Melhor caminho: A -> B -> F.

Do nó A, para G, gasta 18 milissegundos no total da transmissão.
Melhor caminho: A -> D -> G.

Do nó A, para H, gasta 25 milissegundos no total da transmissão.
Melhor caminho: A -> B -> F -> H.

Do nó A, para I, gasta 24 milissegundos no total da transmissão.
Melhor caminho: A -> D -> G -> I.

Do nó A, para J, gasta 34 milissegundos no total da transmissão.
Melhor caminho: A -> D -> G -> I -> J ou A -> B -> F -> H -> J.

Etapa 1

Passo 2

Problema do menor caminho

Problema:
Obter Caminhos interligando Vértices de um Grafo, cujo comprimento (Custo) seja Mínimo.
Implementações:
Algoritmo de Dijkstra
Aplicação:
Redes de Computadores (Percurso entre Roteadores)
Tráfego Urbano.
Sistemas Rodoviários, Ferroviários e Aéreos,
Importante para vários outros problemas

Algoritimo de Dijikstra
Problema dos caminhos mais curtos de origem (fonte) única: para um dado vértice, chamado fonte, em um grafo ponderado conectado, encontrar os caminhos mais curtos a todos os outros vértices
Algoritmo de Dijkstra: melhor algoritmo conhecido aplicado a grafos com pesos não negativos
Encontra os caminhos mais curtos de acordo com a distância a uma dada fonte
Primeiro, encontra o caminho mais curto da fonte ao vértice mais próximo e assim por diante.
Em geral, antes da