Problema do caminho mínimo

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'.

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.
• 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.
• 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.

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.