O problema do caminho mínimo ponderado

Neste problema recebemos como entrada:

 - um grafo G=(V,E), 
 - com comprimentos l(e)>=0 em cada aresta e em E
 - e um vértice origem s
 
E queremos encontrar:

 - o valor do caminho mínimo de s até cada vértice v em V
 - também gostaríamos que esses caminhos fossem devolvidos



Mas, busca em largura não encontrava caminhos mínimos ao explorar o grafo em camadas centradas em s? Por que voltamos a esse problema? O que mudou?

 - R: Busca em largura só funciona em grafos não ponderados, ou seja, naqueles em que toda aresta tem custo uniforme
 
Observe que podemos converter uma entrada do problema de caminhos mínimos ponderados numa entrada não ponderada. Como?

 - R: Substituindo cada aresta e com custo l(e) por um caminho com l(e) arestas e l(e) - 1 novos vértices. Se utilizarmos o algoritmo de busca em largura neste grafo resolvemos o problema de caminhos mínimos ponderado, mas a solução pode não ser eficiente. Por que?
 
    - R: Porque o grafo modificado tem o número de vértices e arestas aumentado em proporção ao comprimento l das arestas. Observe que o grafo modificado pode crescer exponencialmente, pois um valor de comprimento que é representado usando um número k de bits pode implicar um número 2^k de novos vértices.