Mostrar código-fonte de Problema do caminho mínimo

{{Mais notas|data=maio de 2024}}
[[Imagem:Prim Algorithm 0.png|thumb|300px|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 dos grafos|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 <math>f:A \to \R</math>) e, dado qualquer elemento ''v'' de ''V'', encontrar um caminho ''P'' de ''v'' para cada ''v''' de ''V'' tal que

:<math>\sum_{p\in P} f(p)</math>

é 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 <math>v</math> e cada inteiro <math>i \leq k</math> , <math>dist(v,i)</math> como o menor caminho de <math>s</math> até <math>v</math> que usa <math>i</math> arestas. Os valores iniciais de <math>dist(v,0)</math> são <math>\infty</math> para todos os vértices exceto <math>s</math>, para o qual é 0. E a equação geral de atualização é:

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

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]] &nbsp;— 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.<ref>{{citar livro|autor=Christian Pretzsch|título=IT-Case Study: Ontology-Based Answer Selection in Dialog Systems|url=http://books.google.com.br/books?id=E753lIgTIRgC&pg=PA47&dq=Dijkstra's+algorithm+source+vertex+graphs&hl=pt-BR&sa=X&ei=D-J8UoGCDpK1kQejhYGADQ&ved=0CC8Q6AEwAA#v=onepage&q=Dijkstra's%20algorithm%20source%20vertex%20graphs&f=false|ano=2007|editora=VDM Verlag Dr. Mueller e.K|local=USA|isbn=978-3836405102|lingua=inglês}}</ref>
* [[Algoritmo de Bellman-Ford]] &nbsp;— Resolve o problema para grafos com um vértice-fonte e arestas que podem ter pesos negativos.
* [[Algoritmo A*]] &nbsp;— um algoritmo [[Heurística|heurístico]] que calcula o caminho mínimo com um vértice-fonte.
* [[Algoritmo de Floyd-Warshall]] &nbsp;— Determina a distância entre todos os pares de vértices de um grafo.<ref>{{citar livro|sobrenome=Baras|nome=John|título=Path Problems in Networks|ano=2010|editora=Morgan & Claypool Publishers|isbn=9781598299243|autor2=George Theodorakopoulos|página=5|acessodata=7 de Novembro de 2013}}</ref>
* [[Algoritmo de Johnson]] &nbsp;— 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]].
*Algoritmo Viterbi — Resolve o menor problema de caminho estocástico com um peso probabilístico adicional em cada nó.

== Aplicações ==
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|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, entre outros.

Podem ser aplicados para encontrar automaticamente direções entre locais físicos, como instruções de direção em sites de mapeamento da web como o MapQuest ou o [[Google Maps]]. Para esta aplicação, algoritmos especializados rápidos estão disponíveis.

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. Se alguém representa uma [[máquina abstrata]] não determinística como um gráfico em que os vértices descrevem estados e arestas descrevem possíveis transições, algoritmos de caminho mínimo podem ser usados para encontrar uma sequência ótima de opções para atingir um determinado estado objetivo ou para estabelecer limites mais baixos no tempo necessário para atingir um determinado estado. Por exemplo, se os vértices representam os estados de um quebra-cabeça como o [[Cubo de Rubik]] e cada borda direcionada corresponde a um único movimento ou turno, os algoritmos de caminho mínimo podem ser usados para encontrar uma solução que use o número mínimo possível de movimentos. 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.

Uma aplicação mais alegre são os jogos de "[[Teoria dos seis graus de separação|seis graus de separação]]" que tentam encontrar o caminho mais curto em gráficos como estrelas de cinema que aparecem no mesmo filme.

Outras aplicações, frequentemente estudadas em [[pesquisa operacional]], incluem layout de instalações e instalações, [[robótica]], [[transporte]] e design de [[VLSI Technology|VLSI]].

== Redes rodoviárias ==
Uma rede rodoviária pode ser considerada como um gráfico com pesos positivos. Os nós representam cruzamentos e cada aresta do gráfico é associado a um segmento de estrada entre dois cruzamentos. O peso de uma aresta pode corresponder ao comprimento do segmento de estrada associado, ao tempo necessário para atravessar o segmento ou ao custo de atravessar o segmento. Usando arestas direcionadas, também é possível modelar ruas de mão única. Esses gráficos são especiais no sentido de que algumas arestas são mais importantes que outras para viagens de longa distância (por exemplo, rodovias). Esta propriedade foi formalizada usando a noção de dimensão da estrada. Há um grande número de algoritmos que exploram essa propriedade e, portanto, são capazes de calcular o caminho mais curto muito mais rapidamente do que seria possível em gráficos gerais.

Todos esses algoritmos funcionam em duas fases. Na primeira fase, o gráfico é pré-processado sem conhecer o nó de origem ou destino. A segunda fase é a fase de consulta. Nesta fase, o nó de origem e o destino são conhecidos. A ideia é que a rede rodoviária seja estática; portanto, a fase de pré-processamento pode ser realizada uma vez e usada para um grande número de consultas na mesma rede rodoviária.

O algoritmo com o tempo de consulta mais rápido conhecido é chamado de rotulagem de hub e é capaz de calcular o caminho mais curto nas redes rodoviárias da Europa ou dos EUA em uma fração de microssegundo. Outras técnicas que foram usadas são:

* ALT (pesquisa A *, pontos de referência e desigualdade de triângulo)
* Bandeiras de arco
* Hierarquias de contração
* Roteamento do nó de trânsito
* Poda baseada em alcance
* Marcação
* Etiquetas do hub

== Caminho mais curto em redes estocásticas dependentes do tempo ==
Em situações da vida real, a rede de transporte geralmente é estocástica e depende do tempo. De fato, um viajante que atravessa um link diariamente pode experimentar diferentes tempos de viagem nesse link, devido não apenas às flutuações na demanda de viagens (matriz de origem-destino), mas também devido a incidentes como zonas de trabalho, más condições climáticas, acidentes e avarias de veículos. Como resultado, uma rede estocástica dependente do tempo (DST) é uma representação mais realista de uma rede rodoviária real em comparação com a rede determinística.

Apesar dos progressos consideráveis ao longo da década passada, continua sendo uma questão controversa como um caminho ideal deve ser definido e identificado nas redes rodoviárias estocásticas. Em outras palavras, não existe uma definição única de um caminho ideal sob incerteza. Uma resposta possível e comum a essa pergunta é encontrar um caminho com o tempo mínimo de viagem esperado. A principal vantagem do uso dessa abordagem é que algoritmos eficientes de caminho mínimo introduzidos para as redes determinísticas podem ser facilmente empregados para identificar o caminho com o tempo de viagem mínimo esperado em uma rede estocástica. No entanto, o caminho ideal resultante identificado por essa abordagem pode não ser confiável, porque essa abordagem falha em lidar com a variabilidade do tempo de viagem. Para resolver esse problema, alguns pesquisadores usam a distribuição do tempo de viagem em vez do [[valor esperado]] para encontrar a distribuição de probabilidade do tempo total de viagem usando diferentes métodos de otimização, como [[programação dinâmica]] e [[algoritmo de Dijkstra]]. Esses métodos usam otimização estocástica, especificamente estocástica programação dinâmica para encontrar o caminho mais curto em redes com comprimento de arco probabilístico. O conceito de confiabilidade do tempo de viagem é usado de forma intercambiável com a variabilidade do tempo de viagem na literatura de pesquisa em transporte, de modo que, em geral, pode-se dizer que quanto maior a variabilidade no tempo de viagem, menor a confiabilidade e vice-versa.

Para explicar a confiabilidade do tempo de viagem com mais precisão, foram sugeridas duas definições alternativas comuns para um caminho ideal sob incerteza. Alguns introduziram o conceito do caminho mais confiável, com o objetivo de maximizar a probabilidade de chegar a tempo ou antes de um determinado orçamento de tempo de viagem. Outros, em alternativa, propuseram o conceito de um caminho α confiável com base no qual pretendiam minimizar o orçamento de tempo de viagem necessário para garantir uma probabilidade de chegada pontual pré-especificada.

*{{citar livro|autor=Andrew V. Goldberg|título=The Shortest Path Problem (Dimacs Series in Discrete Mathematics and Theoretical Computer Science)|ano=2009|editora=American Mathematical Society|local=USA|isbn=978-0821843833}}

{{Portal3|Matemática}}{{Referências|refs=}}
<references responsive="0"></references>{{refbegin}}
*{{citar periódico|titulo=Faster algorithms for the shortest path problem|url=http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA194031|periódico=Journal of the ACM|volume=37|doi=10.1145/77600.77615|ref=harv|primeiro4=Robert E.|data=abril de 1990|último4=Tarjan|primeiro3=James|primeiro2=Kurt|publicado=ACM|último3=Orlin|número=2|páginas=213–223|último1=Ahuja|primeiro1=Ravindra K.|autorlink4=Robert Tarjan|último2=Mehlhorn}}
* {{citar periódico|titulo=On a routing problem|periódico=Quarterly of Applied Mathematics|volume=16|doi=10.1090/qam/102435|mr=0102435|ref=harv|último=Bellman|primeiro=Richard|ano=1958|páginas=87–90|autorlink=Richard Bellman}}
*{{citar periódico|titulo=Shortest paths algorithms: theory and experimental evaluation|url=http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/sp-alg.ps.Z|periódico=Mathematical Programming|series=Ser. A|volume=73|doi=10.1016/0025-5610(95)00021-6|mr=1392160|ref=harv|primeiro1=Boris V.|último1=Cherkassky|último2=Goldberg|páginas=129–174|número=2|primeiro2=Andrew V.|ano=1996|primeiro3=Tomasz|último3=Radzik|autorlink2==Andrew V. Goldberg}}
* {{Introduction to Algorithms|edição=2|pages=580–642|capítulo=Single-Source Shortest Paths and All-Pairs Shortest Paths}}
*{{citar periódico|titulo=On the Shortest Route through a Network|periódico=Management Science|volume=6|doi=10.1287/mnsc.6.2.187|ref=harv|último=Dantzig|primeiro=G. B.|data=janeiro de 1960|número=2|páginas=187–190}}
*{{citation|primeiro1=Jean Claude|último1=Derniame|primeiro2=Claude|último2=Pair|titulo=Problèmes de cheminement dans les graphes (Path Problems in Graphs)|publicado=Dunod (Paris)|ano=1971}}
* {{citar periódico|titulo=A note on two problems in connexion with graphs|periódico=Numerische Mathematik|volume=1|doi=10.1007/BF01386390|ref=harv|ano=1959|páginas=269–271|último1=Dijkstra|primeiro1=E. W.|autorlink=Edsger W. Dijkstra}}
* {{citar periódico|titulo=Network Flow Theory|url=http://www.rand.org/pubs/papers/P923.html|id=P-923|ref=harv|último=Ford|primeiro=L. R.|publicado=Rand Corporation|data=1956}}<!--cited in Dijkstra 1959-->
* {{citar conferência|último1=Fredman|primeiro1=Michael Lawrence|autorlink1=Michael Fredman|primeiro2=Robert E.|último2=Tarjan|autorlink2=Robert Tarjan|titulo=Fibonacci heaps and their uses in improved network optimization algorithms|conferencia=25th Annual Symposium on Foundations of Computer Science|ano=1984|publicado=[[IEEE]]|páginas=338–346|ref=harv|doi=10.1109/SFCS.1984.715934|isbn=0-8186-0591-X}}
* {{citar periódico|titulo=Fibonacci heaps and their uses in improved network optimization algorithms|periódico=Journal of the Association for Computing Machinery|volume=34|doi=10.1145/28869.28874|ref=harv|último2=Tarjan|primeiro2=Robert E.|ano=1987|número=3|páginas=596–615|último1=Fredman|primeiro1=Michael Lawrence|autorlink1=Michael Fredman|autorlink2=Robert Tarjan}}
* {{citar conferência|último=Gabow|primeiro=H. N.|capítulo=Scaling algorithms for network problems|doi=10.1109/SFCS.1983.68|páginas=248–258|titulo=Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983)|ano=1983|ref=harv|url=http://www.eecs.umich.edu/%7Epettie/matching/Gabow-scaling-algorithms-for-network-problems.pdf}}
*{{citar periódico|titulo=Scaling algorithms for network problems|periódico=[[Journal of Computer and System Sciences]]|volume=31|doi=10.1016/0022-0000(85)90039-X|mr=828519|ref=harv|último=Gabow|primeiro=Harold N.|ano=1985|número=2|páginas=148–168}}
*{{citar livro|url=http://dl.acm.org/citation.cfm?id=686343&CFID=563073233&CFTOKEN=28801665|titulo=Improved Shortest Paths on the Word RAM|último1=Hagerup|primeiro=Torben|isbn=978-3-540-67715-4|ref=harv|ano=2000|páginas=61–72|periódico=Proceedings of the 27th International Colloquium on Automata, Languages and Programming|editor-nome1=Ugo|editor-sobrenome1=Montanari|editor-nome2=José D. P.|editor-sobrenome2=Rolim|editor-nome3=Emo|editor-sobrenome3=Welzl}}
*{{citar periódico|titulo=Efficient algorithms for shortest paths in sparse networks|periódico=[[Journal of the ACM]]|volume=24|doi=10.1145/321992.321993|último=Johnson|primeiro=Donald B.|autorlink=Donald B. Johnson|número=1|páginas=1–13|ano=1977}}
*{{citar periódico|titulo=A priority queue in which initialization and queue operations take {{math|''O''(log log ''D'')}} time|periódico=Mathematical Systems Theory|volume=15|doi=10.1007/BF01786986|mr=683047|ref=harv|último=Johnson|primeiro=Donald B.|data=dezembro de 1981|número=1|páginas=295–309|autorlink=Donald B. Johnson}}
*{{citar periódico|titulo=An {{math|''O''(''m'' log log ''D'')}} algorithm for shortest paths|periódico=[[Discrete Applied Mathematics]]|volume=6|doi=10.1016/0166-218X(83)90104-X|mr=700028|ref=harv|último2=Poblete|primeiro2=Patricio V.|ano=1983|número=1|páginas=91–93|último1=Karlsson|primeiro1=Rolf G.}}
* {{citar livro|titulo=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems|último1=Leyzorek|primeiro1=M.|último2=Gray|primeiro2=R. S.|último3=Johnson|primeiro3=A. A.|último4=Ladew|primeiro4=W. C.|último5=Meaker|primeiro5=S. R., Jr.|último6=Petry|ref=harv|primeiro6=R. M.|último7=Seitz|primeiro7=R. N.|publicado=Case Institute of Technology|ano=1957|local=Cleveland, Ohio}}
* {{citar conferência|último=Moore|primeiro=E. F.|autorlink=Edward F. Moore|ano=1959|titulo=The shortest path through a maze|páginas=285–292|títulolivro=Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957)|publicado=Harvard University Press|local=Cambridge|ref=harv}}
*{{citar livro|url=http://dl.acm.org/citation.cfm?id=545417&CFID=563073233&CFTOKEN=28801665|titulo=Computing shortest paths with comparisons and additions|último1=Pettie|primeiro1=Seth|último2=Ramachandran|primeiro2=Vijaya|isbn=978-0-89871-513-2|ref=harv|ano=2002|páginas=267–276|periódico=Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms}}
*{{citar periódico|titulo=A new approach to all-pairs shortest paths on real-weighted graphs|periódico=Theoretical Computer Science|volume=312|doi=10.1016/s0304-3975(03)00402-x|ref=harv|último=Pettie|primeiro=Seth|data=26 de janeiro de 2004|número=1|páginas=47–74}}
*{{citar periódico|titulo=Solution of the Shortest-Route Problem—A Review|periódico=Oper. Res.|volume=8|doi=10.1287/opre.8.2.224|ref=harv|último1=Pollack|primeiro1=Maurice|último2=Wiebenson|primeiro2=Walter|data=março–abril de 1960|número=2|páginas=224–230}}  Attributes Dijkstra's algorithm to Minty ("private communication") on p.&nbsp;225.
* {{citar livro|titulo=Combinatorial Optimization — Polyhedra and Efficiency|último=Schrijver|primeiro=Alexander|series=Algorithms and Combinatorics|volume=24|isbn=978-3-540-20456-5|ref=harv|publicado=Springer|ano=2004}} Here: vol.A, sect.7.5b, p.&nbsp;103
* {{citar periódico|titulo=Structural parameters of communication networks|periódico=Bulletin of Mathematical Biophysics|volume=15|doi=10.1007/BF02476438|ref=harv|último=Shimbel|primeiro=Alfonso|ano=1953|número=4|páginas=501–507}}
* {{citar conferência|último=Shimbel|primeiro=A.|titulo=Structure in communication nets|local=New York, NY|páginas=199–203|publicado=Polytechnic Press of the Polytechnic Institute of Brooklyn|conferencia=Proceedings of the Symposium on Information Networks|ano=1955|ref=harv}}
*{{citar periódico|titulo=Undirected single-source shortest paths with positive integer weights in linear time|periódico=Journal of the ACM|volume=46|doi=10.1145/316542.316548|ref=harv|data=1999|número=3|páginas=362–394|último1=Thorup|primeiro1=Mikkel}}
*{{citar periódico|titulo=Integer priority queues with decrease key in constant time and the single source shortest paths problem|url=http://dl.acm.org/citation.cfm?id=1039326|periódico=Journal of Computer and System Sciences|volume=69|doi=10.1016/j.jcss.2004.04.003|ref=harv|último=Thorup|primeiro=Mikkel|data=2004|número=3|páginas=330–353|acessodata=}}
*{{citar periódico|titulo=A Method for Finding the Shortest Route through a Road Network|periódico=Operational Research Quarterly|volume=11|doi=10.1057/jors.1960.32|ref=harv|último2=Hillier|primeiro2=J. A.|outros=March–June 1960|número=1/2|páginas=37–40|último1=Whiting|primeiro1=P. D.}}
*{{citar conferência|último=Williams|primeiro=Ryan|autorlink=link=Ryan Williams (computer scientist)|arxiv=1312.6680|capítulo=Faster all-pairs shortest paths via circuit complexity|doi=10.1145/2591796.2591811|mr=3238994|páginas=664–673|publicado=ACM|local=New York|titulo=Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14)|ano=2014|ref=harv|títulolink=Symposium on Theory of Computing}}
{{refend}}

[[Categoria:Teoria dos grafos]]
[[Categoria:Pesquisa operacional]]
[[Categoria:Otimização]]