Problema do caminho mínimo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância de 14.

Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida.

Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um conjunto A de arestas e uma função de peso f:A \to \R) e, dado qualquer elemento v de V, encontrar um caminho P de v para cada v' de V tal que

\sum_{p\in P} f(p)

é mínimo entre todos os caminhos conectando n a n'.

Em programação dinâmica, podemos escolher um subproblema de modo que toda a informação vital seja recordada e levada adiante. Assim, vamos definir que para cada vértice v e cada inteiro i \leq k , dist(v,i) como o menor caminho de s até v que usa i arestas. Os valores iniciais de dist(v,0) são \infty para todos os vértices exceto s, para o qual é 0. E a equação geral de atualização é:

dist(v,i) = \min_{(u,v)\in E} \{dist(u, i - 1) + l(u,v)\}

Existem várias variantes para problemas de caminho mínimo, cada uma adequada a um conjunto de problemas diferente:

  • Problema de único destino: consiste em determinar o menor caminho entre cada um dos nós do grafo e um nó de destino dado.
  • Problema de único origem: determinar o menor caminho entre um nó dado e todos os demais nós do grafo.
  • Problema de origem-destino: determinar o menor caminho entre nós dados.
  • Problemas de todos os pares: determinar o menor caminho entre cada par de nós presentes no grafo.

Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são:

  • Algoritmo de Dijkstra  — Resolve o problema com um vértice-fonte em grafos cujas arestas tenham peso maior ou igual a zero. Sem reduzir o desempenho, este algoritmo é capaz de determinar o caminho mínimo, partindo de um vértice de início v para todos os outros vértices do grafo.[1]
  • Algoritmo de Bellman-Ford  — Resolve o problema para grafos com um vértice-fonte e arestas que podem ter pesos negativos.
  • Algoritmo A*  — um algoritmo heurístico que calcula o caminho mínimo com um vértice-fonte.
  • Algoritmo de Floyd-Warshall  — Determina a distância entre todos os pares de vértices de um grafo.[2]
  • Algoritmo de Johnson  — Determina a distância entre todos os pares de vértices de um grafo, pode ser mais veloz que o algoritmo de Floyd-Warshall em grafos esparsos.

O problema de caminho mínimo é um dos problemas genéricos intensamente estudados e utilizados em diversas áreas como Engenharia de Transportes, Pesquisa Operacional, Ciência da Computação e Inteligência Artificial. Isso decorre do seu potencial de aplicação a inúmeros problemas práticos que ocorrem em transportes, logística, redes de computadores e de telecomunicações, etc.

Outras possibilidades de aplicação incluem quaisquer problemas envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, perdas, ganhos, despesas) que se acumulem linearmente ao longo do percurso da rede.

Um problema relacionado é o Problema do Caixeiro-viajante, que consiste em determinar o caminho mais curto que passa exatamente uma vez por cada vértice e retorna ao vértice de partida. Este é um problema NP-Completo, para os quais não há uma solução eficiente.

Referências

  1. Christian Pretzsch. IT-Case Study: Ontology-Based Answer Selection in Dialog Systems (em inglês). USA: VDM Verlag Dr. Mueller e.K, 2007. ISBN 978-3836405102.
  2. Baras, John; George Theodorakopoulos. Path Problems in Networks. [S.l.]: Morgan & Claypool Publishers, 2010. p. 5. ISBN 9781598299243. Visitado em 7 de Novembro de 2013.
  • Andrew V. Goldberg. The Shortest Path Problem (Dimacs Series in Discrete Mathematics and Theoretical Computer Science). USA: American Mathematical Society, 2009. ISBN 978-0821843833.