problema do caminho mínimo

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 ) e, dado qualquer elemento v de V, encontrar um caminho P de v para cada v' de V tal que é 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 e cada inteiro , como o menor caminho de até que usa arestas. Os valores iniciais de são para todos os vértices exceto , para o qual é 0. E a equação geral de atualização é: 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. * 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 . * Algoritmo Viterbi — Resolve o menor problema de caminho estocástico com um peso probabilístico adicional em cada nó.