Problema de caminho mais curto - Shortest path problem
Na teoria dos grafos , o problema do caminho mais curto é encontrar um caminho entre dois vértices (ou nós) em um grafo de forma que a soma dos pesos de suas arestas constituintes seja minimizada.
O problema de encontrar o caminho mais curto entre duas interseções em um mapa rodoviário pode ser modelado como um caso especial do problema do caminho mais curto em gráficos, onde os vértices correspondem a interseções e as bordas correspondem a segmentos de estrada, cada um ponderado pelo comprimento do segmento.
Definição
O problema do caminho mais curto pode ser definido para gráficos, sejam eles não direcionados , direcionados ou mistos . É definido aqui para gráficos não direcionados; para gráficos direcionados, a definição de caminho requer que vértices consecutivos sejam conectados por uma aresta direcionada apropriada.
Dois vértices são adjacentes quando ambos incidem em uma aresta comum. Um caminho em um gráfico não dirigida é uma sequência de vértices de tal modo que é adjacente ao para . Esse caminho é chamado de caminho de comprimento de para . (As variáveis são; sua numeração aqui se relaciona à sua posição na sequência e não precisa estar relacionada a nenhuma marcação canônica dos vértices.)
Deixe ser o incidente de ponta para ambos e . Dada uma função de peso com valor real e um gráfico não direcionado (simples) , o caminho mais curto de para é o caminho (onde e ) que, de maneira geral, minimiza a soma. Quando cada aresta no gráfico tem peso unitário ou , isso é equivalente a encontrar o caminho com menos arestas.
O problema também é às vezes chamado de problema do caminho mais curto de par único , para distingui-lo das seguintes variações:
- O problema do caminho mais curto de fonte única , em que temos que encontrar os caminhos mais curtos de um vértice de origem v para todos os outros vértices no gráfico.
- O problema do caminho mais curto de destino único , em que temos que encontrar os caminhos mais curtos de todos os vértices no grafo direcionado para um único vértice de destino v . Isso pode ser reduzido ao problema do caminho mais curto de fonte única, invertendo os arcos no gráfico direcionado.
- O problema do caminho mais curto com todos os pares , em que temos que encontrar os caminhos mais curtos entre cada par de vértices v , v ' no gráfico.
Essas generalizações têm algoritmos significativamente mais eficientes do que a abordagem simplista de executar um algoritmo de caminho mais curto de par único em todos os pares de vértices relevantes.
Algoritmos
Os algoritmos mais importantes para resolver este problema são:
- O algoritmo de Dijkstra resolve o problema do caminho mais curto de fonte única com peso de aresta não negativo.
- O algoritmo Bellman-Ford resolve o problema de fonte única se os pesos das arestas puderem ser negativos.
- Um algoritmo de pesquisa * resolve o caminho mais curto de par único usando heurísticas para tentar acelerar a pesquisa.
- O algoritmo Floyd – Warshall resolve todos os caminhos mais curtos dos pares.
- O algoritmo de Johnson resolve todos os caminhos mais curtos dos pares e pode ser mais rápido do que Floyd – Warshall em gráficos esparsos .
- O algoritmo de Viterbi resolve o problema do caminho estocástico mais curto com um peso probabilístico adicional em cada nó.
Algoritmos adicionais e avaliações associadas podem ser encontrados em Cherkassky, Goldberg & Radzik (1996) .
Caminhos mais curtos de fonte única
Gráficos não direcionados
Pesos | Complexidade de tempo | Autor |
---|---|---|
ℝ + | O ( V 2 ) | Dijkstra 1959 |
ℝ + | O (( E + V ) log V ) | Johnson 1977 ( heap binário ) |
ℝ + | O ( E + V log V ) | Fredman & Tarjan 1984 ( pilha de Fibonacci ) |
ℕ | O ( E ) | Thorup 1999 (requer multiplicação em tempo constante) |
Gráficos não ponderados
Algoritmo | Complexidade de tempo | Autor |
---|---|---|
Pesquisa abrangente | O ( E + V ) |
Gráficos acíclicos direcionados (DAGs)
Um algoritmo usando classificação topológica pode resolver o problema do caminho mais curto de fonte única no tempo Θ ( E + V ) em DAGs arbitrariamente ponderados.
Gráficos direcionados com pesos não negativos
A tabela a seguir foi retirada de Schrijver (2004) , com algumas correções e acréscimos. Um fundo verde indica um melhor limite assintoticamente na tabela; L é o comprimento máximo (ou peso) entre todas as arestas, assumindo pesos de aresta inteiros.
Pesos | Algoritmo | Complexidade de tempo | Autor |
---|---|---|---|
ℝ | O ( V 2 EL ) | Ford 1956 | |
ℝ | Algoritmo Bellman-Ford | O ( VE ) | Shimbel 1955 , Bellman 1958 , Moore 1959 |
ℝ | O ( V 2 log V ) | Dantzig 1960 | |
ℝ | Algoritmo de Dijkstra com lista | O ( V 2 ) | Leyzorek et al. 1957 , Dijkstra 1959 , Minty (ver Pollack & Wiebenson 1960 ), Whiting & Hillier 1960 |
ℝ | Algoritmo de Dijkstra com heap binário | O (( E + V ) log V ) | Johnson 1977 |
ℝ | Algoritmo de Dijkstra com heap de Fibonacci | O ( E + V log V ) | Fredman & Tarjan 1984 , Fredman & Tarjan 1987 |
ℕ | Algoritmo de Dial (algoritmo de Dijkstra usando uma fila de depósitos com L depósitos ) | O ( E + LV ) | Disque 1969 |
O ( E log log L ) | Johnson 1981 , Karlsson & Poblete 1983 | ||
Algoritmo de Gabow | O ( E log E / V L ) | Gabow 1983 , Gabow 1985 | |
O ( E + V √ log L ) | Ahuja et al. 1990 | ||
Thorup | O ( E + V log log V ) | Thorup 2004 |
Gráficos direcionados com pesos arbitrários sem ciclos negativos
Pesos | Algoritmo | Complexidade de tempo | Autor |
---|---|---|---|
ℝ | O ( V 2 EL ) | Ford 1956 | |
ℝ | Algoritmo Bellman-Ford | O ( VE ) | Shimbel 1955 , Bellman 1958 , Moore 1959 |
ℝ | Johnson-Dijkstra com heap binário | O ( V ( E + log V )) | Johnson 1977 |
ℝ | Johnson-Dijkstra com pilha de Fibonacci | O ( V ( E + log V )) | Fredman & Tarjan 1984 , Fredman & Tarjan 1987 , adaptado após Johnson 1977 |
ℕ | Técnica de Johnson aplicada ao algoritmo de Dial | O ( V ( E + L )) | Disque 1969 , adaptado após Johnson 1977 |
Gráficos direcionados planares com pesos arbitrários
Caminhos mais curtos de todos os pares
O problema do caminho mais curto com todos os pares encontra os caminhos mais curtos entre cada par de vértices v , v ' no gráfico. O problema de caminhos mais curtos de todos os pares para grafos direcionados não ponderados foi introduzido por Shimbel (1953) , que observou que poderia ser resolvido por um número linear de multiplicações de matrizes que levam um tempo total de O ( V 4 ) .
Gráfico não direcionado
Pesos | Complexidade de tempo | Algoritmo |
---|---|---|
ℝ + | O ( V 3 ) | Algoritmo Floyd – Warshall |
Algoritmo de Seidel (tempo de execução esperado) | ||
ℕ | Williams 2014 | |
ℝ + | O ( EV log α ( E , V )) | Pettie & Ramachandran 2002 |
ℕ | O ( EV ) | Thorup 1999 aplicado a todos os vértices (requer multiplicação em tempo constante). |
Gráfico direcionado
Pesos | Complexidade de tempo | Algoritmo |
---|---|---|
ℝ (sem ciclos negativos) | O ( V 3 ) | Algoritmo Floyd – Warshall |
ℕ | Williams 2014 | |
ℝ (sem ciclos negativos) | O ( EV + V 2 log V ) | Johnson – Dijkstra |
ℝ (sem ciclos negativos) | O ( EV + V 2 log log V ) | Pettie 2004 |
ℕ | O ( EV + V 2 log log V ) | Hagerup 2000 |
Formulários
Os algoritmos do caminho mais curto são aplicados para encontrar automaticamente as direções entre locais físicos, como direções de direção em sites de mapeamento da web como MapQuest ou Google Maps . Para esta aplicação, algoritmos especializados rápidos estão disponíveis.
Se alguém representa uma máquina abstrata não determinística como um gráfico onde vértices descrevem estados e arestas descrevem transições possíveis, algoritmos de caminho mais curto podem ser usados para encontrar uma sequência ótima de escolhas para atingir um determinado estado objetivo, ou para estabelecer limites inferiores no tempo necessário para atingir um determinado estado. Por exemplo, se os vértices representam os estados de um quebra-cabeça como um cubo de Rubik e cada aresta direcionada corresponde a um único movimento ou giro, algoritmos de caminho mais curto podem ser usados para encontrar uma solução que use o número mínimo possível de movimentos.
Em uma mentalidade de rede ou telecomunicações , esse problema de caminho mais curto às vezes é chamado de problema de caminho de atraso mínimo e geralmente vinculado a um problema de caminho mais amplo . Por exemplo, o algoritmo pode buscar o caminho mais curto mais curto (atraso mínimo) ou o caminho mais curto mais largo (atraso mínimo).
Uma aplicação mais leve são os jogos de " seis graus de separação " que tentam encontrar o caminho mais curto em gráficos como estrelas de cinema aparecendo no mesmo filme.
Outras aplicações, frequentemente estudadas em pesquisa operacional , incluem o layout da planta e das instalações, robótica , transporte e projeto VLSI .
Redes de estradas
Uma rede rodoviária pode ser considerada um gráfico com pesos positivos. Os nós representam cruzamentos de estradas e cada borda do gráfico está associada a um segmento de estrada entre dois cruzamentos. O peso de uma borda pode corresponder ao comprimento do segmento de estrada associado, o tempo necessário para atravessar o segmento ou o custo de atravessar o segmento. Usando bordas 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 do que outras para viagens de longa distância (por exemplo, rodovias). Essa propriedade foi formalizada a partir da noção de dimensão da rodovia. Há um grande número de algoritmos que exploram essa propriedade e, portanto, são capazes de calcular o caminho mais curto muito mais rápido 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, os nós de origem e destino são conhecidos. A ideia é que a malha viária seja estática, de modo que a fase de pré-processamento pode ser feita uma vez e utilizada para um grande número de consultas na mesma malha viária.
O algoritmo com o tempo de consulta conhecido mais rápido é chamado de rotulagem de hub e é capaz de calcular o caminho mais curto nas redes rodoviárias da Europa ou dos Estados Unidos em uma fração de microssegundo. Outras técnicas utilizadas são:
- ALT ( pesquisa A * , pontos de referência e desigualdade triangular )
- Bandeiras de arco
- Hierarquias de contração
- Roteamento de nó de trânsito
- Poda baseada em alcance
- Marcação
- Rótulos de hub
Problemas relacionados
Para problemas de caminho mais curto em geometria computacional , consulte Caminho mais curto euclidiano .
O problema do caixeiro viajante é encontrar o caminho mais curto que atravessa cada vértice exatamente uma vez e retorna ao início. Ao contrário do problema do caminho mais curto, que pode ser resolvido em tempo polinomial em gráficos sem ciclos negativos, o problema do caixeiro viajante é NP-completo e, como tal, acredita-se que não seja eficientemente solucionável para grandes conjuntos de dados (ver problema P = NP ) O problema de encontrar o caminho mais longo em um gráfico também é NP-completo.
O problema do viajante canadense e o problema do caminho mais curto estocástico são generalizações em que o gráfico não é completamente conhecido pelo motor, muda ao longo do tempo ou onde as ações (travessias) são probabilísticas.
O caminho múltiplo desconectado mais curto é uma representação da rede de caminhos primitivos dentro da estrutura da teoria Reptation .
O problema do caminho mais amplo busca um caminho de forma que o rótulo mínimo de qualquer aresta seja o maior possível.
Caminhos mais curtos estratégicos
Às vezes, as arestas de um gráfico têm personalidades: cada aresta tem seu próprio interesse egoísta. Um exemplo é uma rede de comunicação, em que cada ponta é um computador que possivelmente pertence a uma pessoa diferente. Computadores diferentes têm velocidades de transmissão diferentes, então cada borda da rede tem um peso numérico igual ao número de milissegundos que leva para transmitir uma mensagem. Nosso objetivo é enviar uma mensagem entre dois pontos da rede no menor tempo possível. Se soubermos o tempo de transmissão de cada computador (o peso de cada aresta), podemos usar um algoritmo de caminhos mais curtos padrão. Se não soubermos os tempos de transmissão, teremos que pedir a cada computador que nos diga seu tempo de transmissão. Mas, os computadores podem ser egoístas: um computador pode nos dizer que seu tempo de transmissão é muito longo, de modo que não o incomodaremos com nossas mensagens. Uma possível solução para esse problema é usar uma variante do mecanismo VCG , que dá aos computadores um incentivo para revelar seus verdadeiros pesos.
Formulação de programação linear
Existe uma formulação de programação linear natural para o problema do caminho mais curto, fornecida a seguir. É muito simples em comparação com a maioria dos outros usos de programas lineares na otimização discreta , no entanto, ilustra conexões com outros conceitos.
Dado um gráfico direcionado ( V , A ) com o nó de origem s , o nó de destino t e o custo w ij para cada aresta ( i , j ) em A , considere o programa com as variáveis x ij
- minimizar sujeito a e para todos eu ,
A intuição por trás disso é que é uma variável indicadora de se a aresta ( i , j ) faz parte do caminho mais curto: 1 quando é e 0 se não é. Queremos selecionar o conjunto de arestas com peso mínimo, sujeito à restrição de que este conjunto forma um caminho de s até t (representado pela restrição de igualdade: para todos os vértices exceto s e t o número de arestas de entrada e saída que fazem parte do caminho deve ser o mesmo (ou seja, deve ser um caminho de s para t).
Este LP tem a propriedade especial de ser integral; mais especificamente, cada solução ótima básica (quando existe uma) tem todas as variáveis iguais a 0 ou 1, e o conjunto de arestas cujas variáveis são iguais a 1 formam um dipath s - t . Veja Ahuja et al. para uma prova, embora a origem desta abordagem remonta a meados do século XX.
O duplo para este programa linear é
- maximizar y t - y s sujeito a para todos ij , y j - y i ≤ w ij
e duais viáveis correspondem ao conceito de uma heurística consistente para o algoritmo A * para caminhos mais curtos. Para qualquer dual y viável, os custos reduzidos são não negativos e A * essencialmente executa o algoritmo de Dijkstra nesses custos reduzidos.
Estrutura algébrica geral em semirings: o problema do caminho algébrico
Muitos problemas podem ser enquadrados como uma forma do caminho mais curto para algumas noções adequadamente substituídas de adição ao longo de um caminho e obtenção do mínimo. A abordagem geral para isso é considerar as duas operações como sendo as de uma semiação . A multiplicação de semiring é feita ao longo do caminho, e a adição é entre caminhos. Essa estrutura geral é conhecida como o problema do caminho algébrico .
A maioria dos algoritmos de caminho mais curto clássicos (e os novos) podem ser formulados como sistemas lineares de resolução de tais estruturas algébricas.
Mais recentemente, uma estrutura ainda mais geral para resolver esses (e muito menos problemas obviamente relacionados) foi desenvolvida sob a bandeira de álgebras de avaliação .
Caminho mais curto em redes dependentes do tempo estocásticas
Em situações da vida real, a rede de transporte é geralmente estocástica e dependente do tempo. Na verdade, 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 viagem (matriz 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 (STD) é uma representação mais realista de uma rede rodoviária real em comparação com a rede determinística.
Apesar do progresso considerável durante a última década, permanece uma questão controversa como um caminho ideal deve ser definido e identificado em redes rodoviárias estocásticas. Em outras palavras, não existe uma definição única de um caminho ótimo sob incerteza. Uma resposta possível e comum para essa pergunta é encontrar um caminho com o tempo mínimo de viagem esperado. A principal vantagem de usar essa abordagem é que algoritmos de caminho mais curto eficientes introduzidos para as redes determinísticas podem ser prontamente 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 esta abordagem pode não ser confiável, porque esta 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 a programação dinâmica e o algoritmo de Dijkstra . Esses métodos usam otimização estocástica , especificamente programação dinâmica estocástica para encontrar o caminho mais curto em redes com comprimento de arco probabilístico. O conceito de confiabilidade do tempo de viagem é utilizado 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 seria a confiabilidade e vice-versa.
A fim de contabilizar a confiabilidade do tempo de viagem com mais precisão, duas definições alternativas comuns para um caminho ideal sob incerteza foram sugeridas. 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, alternativamente, 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 no tempo pré-especificada.
Veja também
- Pesquisa bidirecional , um algoritmo que encontra o caminho mais curto entre dois vértices em um gráfico direcionado
- Caminho euclidiano mais curto
- Rede de fluxo
- K rota de caminho mais curto
- Multiplicação da matriz Min-plus
- Encontrando o caminho
- Ponte do caminho mais curto
- Árvore do caminho mais curto
Referências
Notas
Bibliografia
- Ahuja, Ravindra K .; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (abril de 1990). "Algoritmos mais rápidos para o problema do caminho mais curto" . Jornal do ACM . ACM. 37 (2): 213–223. doi : 10.1145 / 77600.77615 . hdl : 1721,1 / 47994 . S2CID 5499589 .
- Bellman, Richard (1958). "Em um problema de roteamento" . Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090 / qam / 102435 . MR 0102435 .
- Cherkassky, Boris V .; Goldberg, Andrew V .; Radzik, Tomasz (1996). "Algoritmos de caminhos mais curtos: teoria e avaliação experimental" . Programação matemática . Ser. A. 73 (2): 129-174. doi : 10.1016 / 0025-5610 (95) 00021-6 . MR 1392160 .
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Caminhos mais curtos de fonte única e caminhos mais curtos de todos os pares". Introdução aos Algoritmos (2ª ed.). MIT Press e McGraw-Hill. pp. 580–642. ISBN 0-262-03293-7.
- Dantzig, GB (janeiro de 1960). "No caminho mais curto através de uma rede". Ciência da Administração . 6 (2): 187–190. doi : 10.1287 / mnsc.6.2.187 .
- Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs) , Dunod (Paris)
- Dijkstra, EW (1959). "Uma nota sobre dois problemas na conexão com gráficos". Numerische Mathematik . 1 : 269–271. doi : 10.1007 / BF01386390 . S2CID 123284777 .
-
Ford, LR (1956). "Teoria do Fluxo da Rede" . Rand Corporation. P-923. Citar diário requer
|journal=
( ajuda ) - Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Fibonacci heaps e seus usos em algoritmos de otimização de rede aprimorados . 25º Simpósio Anual de Fundamentos da Ciência da Computação. IEEE . pp. 338–346. doi : 10.1109 / SFCS.1984.715934 . ISBN 0-8186-0591-X.
- Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Fibonacci heaps e seus usos em algoritmos de otimização de rede aprimorados". Journal of the Association for Computing Machinery . 34 (3): 596–615. doi : 10.1145 / 28869.28874 . S2CID 7904683 .
- Gabow, HN (1983). “Algoritmos de escalonamento para problemas de rede”. Anais do 24º Simpósio Anual sobre Fundamentos de Ciência da Computação (FOCS 1983) (PDF) . pp. 248-258. doi : 10.1109 / SFCS.1983.68 .
- Gabow, Harold N. (1985). "Algoritmos de escalonamento para problemas de rede" . Journal of Computer and System Sciences . 31 (2): 148–168. doi : 10.1016 / 0022-0000 (85) 90039-X . MR 0828519 .
- Hagerup, Torben (2000). Montanari, Ugo; Rolim, José DP; Welzl, Emo (eds.). Caminhos mais curtos aprimorados na RAM do Word . Anais do 27º Colóquio Internacional sobre Autômatos, Linguagens e Programação . pp. 61–72. ISBN 978-3-540-67715-4.
- Johnson, Donald B. (1977). "Algoritmos eficientes para caminhos mais curtos em redes esparsas". Jornal do ACM . 24 (1): 1–13. doi : 10.1145 / 321992.321993 . S2CID 207678246 .
- Altıntaş, Gökhan (2020). Soluções exatas para problemas de caminho mais curto com base em analogias mecânicas: em conexão com labirintos . Amazon Digital Services LLC. p. 97. ISBN 9798655831896.
- Johnson, Donald B. (dezembro de 1981). "Uma fila de prioridade em que as operações de inicialização e fila levam tempo O (log log D ) ". Teoria Matemática de Sistemas . 15 (1): 295–309. doi : 10.1007 / BF01786986 . MR 0683047 . S2CID 35703411 .
- Karlsson, Rolf G .; Poblete, Patricio V. (1983). "Um algoritmo O ( m log log D ) para caminhos mais curtos" . Matemática Aplicada Discreta . 6 (1): 91–93. doi : 10.1016 / 0166-218X (83) 90104-X . MR 0700028 .
- Leyzorek, M .; Gray, RS; Johnson, AA; Ladew, WC; Meaker, SR, Jr .; Petry, RM; Seitz, RN (1957). Investigação de Técnicas de Modelo - Primeiro Relatório Anual - 6 de junho de 1956 - 1 de julho de 1957 - Um Estudo de Técnicas de Modelo para Sistemas de Comunicação . Cleveland, Ohio: Case Institute of Technology.
- Moore, EF (1959). "O caminho mais curto através de um labirinto". Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 de abril de 1957) . Cambridge: Harvard University Press. pp. 285–292.
- Pettie, Seth; Ramachandran, Vijaya (2002). Calculando caminhos mais curtos com comparações e acréscimos . Procedimentos do Décimo Terceiro Simpósio Anual ACM-SIAM sobre Algoritmos Discretos . pp. 267–276 . ISBN 978-0-89871-513-2.
- Pettie, Seth (26 de janeiro de 2004). "Uma nova abordagem para caminhos mais curtos de todos os pares em gráficos de peso real" . Ciência da Computação Teórica . 312 (1): 47–74. doi : 10.1016 / s0304-3975 (03) 00402-x .
- Pollack, Maurice; Wiebenson, Walter (março-abril de 1960). "Solução do problema da rota mais curta - Uma revisão". Oper. Res . 8 (2): 224–230. doi : 10.1287 / opre.8.2.224 . Atribui o algoritmo de Dijkstra a Minty ("comunicação privada") na pág. 225
- Schrijver, Alexander (2004). Otimização Combinatória - Poliedros e Eficiência . Algoritmos e Combinatória. 24 . Springer. ISBN 978-3-540-20456-5.Aqui: vol.A, seção.7.5b, p. 103
- Shimbel, Alfonso (1953). “Parâmetros estruturais das redes de comunicação”. Bulletin of Mathematical Biophysics . 15 (4): 501–507. doi : 10.1007 / BF02476438 .
- Shimbel, A. (1955). Estrutura em redes de comunicação . Anais do Simpósio sobre Redes de Informação. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
- Thorup, Mikkel (1999). "Caminhos mais curtos de fonte única não direcionados com pesos inteiros positivos em tempo linear". Jornal do ACM . 46 (3): 362–394. doi : 10.1145 / 316542.316548 . S2CID 207654795 .
- Thorup, Mikkel (2004). "Filas de prioridade inteira com chave de diminuição em tempo constante e o problema de caminhos mais curtos de fonte única" . Journal of Computer and System Sciences . 69 (3): 330–353. doi : 10.1016 / j.jcss.2004.04.003 .
- Whiting, PD; Hillier, JA (março-junho de 1960). "Um método para encontrar a rota mais curta através de uma rede de estradas". Operational Research Quarterly . 11 (1/2): 37–40. doi : 10.1057 / jors.1960.32 .
- Williams, Ryan (2014). "Caminhos mais curtos de todos os pares mais rápidos através da complexidade do circuito". Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14) . Nova York: ACM. pp. 664–673. arXiv : 1312,6680 . doi : 10.1145 / 2591796.2591811 . MR 3238994 .
Leitura adicional
- Frigioni, D .; Marchetti-Spaccamela, A .; Nanni, U. (1998). "Problema de caminho mais curto de fonte única limitada de saída totalmente dinâmica". Proc. 7th Annu. ACM-SIAM Symp. Algoritmos discretos . Atlanta, GA. pp. 212–221. CiteSeerX 10.1.1.32.9856 .
- Dreyfus, SE (outubro de 1967). Uma avaliação de alguns algoritmos de caminho mais curto (PDF) (relatório). Projeto Rand. Força Aérea dos Estados Unidos. RM-5433-PR. DTIC AD-661265.