5058:
numeric weight equal to the number of milliseconds it takes to transmit a message. Our goal is to send a message between two points in the network in the shortest time possible. If we know the transmission-time of each computer (the weight of each edge), then we can use a standard shortest-paths algorithm. If we do not know the transmission times, then we have to ask each computer to tell us its transmission-time. But, the computers may be selfish: a computer might tell us that its transmission time is very long, so that we will not bother it with our messages. A possible solution to this problem is to use
36:
93:
4863:
segment, or the cost of traversing the segment. Using directed edges it is also possible to model one-way streets. Such graphs are special in the sense that some edges are more important than others for long-distance travel (e.g. highways). This property has been formalized using the notion of highway dimension. There are a great number of algorithms that exploit this property and are therefore able to compute the shortest path a lot quicker than would be possible on general graphs.
5147:
4997:
3631:
2389:
5204:
In real-life, a transportation network is usually stochastic and time-dependent. The travel duration on a road segment depends on many factors such as the amount of traffic (origin-destination matrix), road work, weather, accidents and vehicle breakdowns. A more realistic model of such a road network
5208:
There is no accepted definition of optimal path under uncertainty (that is, in stochastic road networks). It is a controversial subject, despite considerable progress during the past decade. One common definition is a path with the minimum expected travel time. The main advantage of this approach is
4862:
A road network can be considered as a graph with positive weights. The nodes represent road junctions and each edge of the graph is associated with a road segment between two junctions. The weight of an edge may correspond to the length of the associated road segment, the time needed to traverse the
4808:
as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represent the
3868:
are a fundamental concept in graph theory and operations research, often used to model problems involving the transportation of goods, liquids, or information through a network. A network flow problem typically involves a directed graph where each edge represents a pipe, wire, or road, and each edge
127:
The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length or distance of each segment.
5057:
Sometimes, the edges in a graph have personalities: each edge has its own selfish interest. An example is a communication network, in which each edge is a computer that possibly belongs to a different person. Different computers have different transmission speeds, so every edge in the network has a
4866:
All of these algorithms work in two phases. In the first phase, the graph is preprocessed without knowing the source or target node. The second phase is the query phase. In this phase, source and target node are known. The idea is that the road network is static, so the preprocessing phase can be
4951:, and are harder to solve. One example is the constrained shortest path problem, which attempts to minimize the total cost of the path while at the same time maintaining another metric below a given threshold. This makes the problem
5177:
Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum. The general approach to these is to consider the two operations to be those of a
4870:
The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the US in a fraction of a microsecond. Other techniques that have been used are:
3875:
can be used to solve certain network flow problems, particularly when dealing with single-source, single-sink networks. In these scenarios, we can transform the network flow problem into a series of shortest path problems.
256:
5212:
To tackle this issue, some researchers use travel duration distribution instead of its expected value. So, they find the probability distribution of total travel duration using different optimization methods such as
6029:
Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm".
5744:
Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Optimal
Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search".
5209:
that it can make use of efficient shortest path algorithms for deterministic networks. However, the resulting optimal path may not be reliable, because this approach fails to address travel time variability.
4946:
Unlike the shortest path problem, which can be solved in polynomial time in graphs without negative cycles, shortest path problems which include additional constraints on the desired solution path are called
3276:
2979:
4534:
4238:
4983:
and the stochastic shortest path problem are generalizations where either the graph is not completely known to the mover, changes over time, or where actions (traversals) are probabilistic.
953:
784:
2004:
648:
3125:
5070:
In some cases, the main goal is not to find the shortest path, but only to detect if the graph contains a negative cycle. Some shortest-paths algorithms can be used for this purpose:
3607:
2284:
3755:
4620:
3816:
2372:
1042:
These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices.
4125:
3501:
991:
3406:
2146:
7090:
2218:
1822:
1645:
1908:
4079:
2755:
2668:
855:
523:
4752:
4701:
4650:
4564:
4452:
4384:
4321:
4268:
4156:
4024:
3705:
3531:
3443:
3313:
3162:
3016:
2878:
2793:
2698:
2611:
2535:
2460:
2314:
2032:
1942:
1852:
1760:
1675:
1595:
1519:
1444:
1302:
1246:
1190:
1147:
348:
3913:
Use a shortest path algorithm (e.g., Dijkstra's algorithm, Bellman-Ford algorithm) to find the shortest path from the source node to the sink node in the residual graph.
2505:
1489:
5128:
3341:
3048:
2844:
152:. Here it is defined for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge.
4422:
1718:
2086:
817:
713:
556:
316:
4813:
and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.
3869:
has a capacity, which is the maximum amount that can flow through it. The goal is to find a feasible flow that maximizes the flow from a source node to a sink node.
7339:
2573:
1557:
610:
583:
475:
448:
421:
283:
5897:
Pair, Claude (1967). "Sur des algorithmes pour des problèmes de cheminement dans les graphes finis" [On algorithms for path problems in finite graphs]. In
3848:
394:
875:
688:
668:
368:
166:
7083:
5059:
6506:
5192:
More recently, an even more general framework for solving these (and much less obviously related problems) has been developed under the banner of
4967:(TSP). The TSP is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. The problem of
477:
are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)
6084:
Olya, Mohammad Hessam (2014). "Applying
Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length".
5682:
Kroger, Martin (2005). "Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems".
7191:
5018:
6836:
6768:
6550:
6237:
6004:
5979:
5954:
5772:
5354:
3616:
3415:
3285:
3134:
2988:
6732:
Investigation of Model
Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems
6210:
Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian (2022). "Negative-Weight Single-Source
Shortest Paths in Near-linear Time".
2163:
7076:
5519:
5189:
Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures.
5652:
5233:
are used as opposites in the transportation research literature: the higher the variability, the lower the reliability of predictions.
7169:
6959:
5587:
5529:
7334:
7020:
6418:
6318:
6019:
Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
5504:
5488:
5044:
79:
57:
6965:
6474:
5833:
5382:
Dürr, Christoph; Heiligman, Mark; Høyer, Peter; Mhalla, Mehdi (January 2006). "Quantum query complexity of some graph problems".
7057:
4789:
Shortest path algorithms are applied to automatically find directions between physical locations, such as driving directions on
4948:
7030:
Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Fully dynamic output bounded single source shortest path problem".
5236:
To account for variability, researchers have suggested two alternative definitions for an optimal path under uncertainty. The
3175:
7256:
6057:
Olya, Mohammad Hessam (2014). "Finding shortest path in a combined exponential – gamma probability distribution arc length".
5274:
5225:, specifically stochastic dynamic programming to find the shortest path in networks with probabilistic arc length. The terms
5022:
3929:
Decrease the capacity of the edges in the forward direction and increase the capacity of the edges in the backward direction.
121:
5182:. Semiring multiplication is done along the path, and the addition is between paths. This general framework is known as the
2890:
7174:
7246:
6161:
4426:
4043:
1072:
6699:
4851:
4458:
4162:
145:
141:
137:
117:
7344:
5566:
Nayebi, Aran; Williams, V. V. (2014-10-22). "Quantum algorithms for shortest paths problems in structured instances".
3638:
2396:
7236:
5075:
2539:
1523:
1060:
6938:
Whiting, P. D.; Hillier, J. A. (March–June 1960). "A Method for
Finding the Shortest Route through a Road Network".
880:
6538:
6308:
4980:
4964:
4927:
The shortest multiple disconnected path is a representation of the primitive path network within the framework of
4821:
718:
5670:
research.microsoft.com/pubs/142356/HL-TR.pdf "A Hub-Based
Labeling Algorithm for Shortest Paths on Road Networks"
4832:
4828:. For example, the algorithm may seek the shortest (min-delay) widest path, or widest shortest (min-delay) path.
1955:
1019:, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex
619:
7279:
7294:
6744:
Proceedings of an
International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957)
6730:
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R. Jr.; Petry, R. M.; Seitz, R. N. (1957).
5007:
4963:
example requires a specific set of vertices to be included in the path, which makes the problem similar to the
3972:, who observed that it could be solved by a linear number of matrix multiplications that takes a total time of
3055:
1401:, with some corrections and additions. A green background indicates an asymptotically best bound in the table;
50:
44:
3540:
2239:
5717:
Lozano, Leonardo; Medaglia, Andrés L (2013). "On an exact method for the constrained shortest path problem".
3713:
1023:. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
7329:
7324:
7241:
7213:
5269:
5259:
5222:
5218:
5026:
5011:
4921:
4889:
4571:
2037:
1856:
1764:
1679:
1054:
7120:
6805:
Pollack, Maurice; Wiebenson, Walter (March–April 1960). "Solution of the
Shortest-Route Problem—A Review".
5613:
Chen, Danny Z. (December 1996). "Developing algorithms and software for geometric path planning problems".
4824:
mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a
3789:
2323:
7284:
7251:
7132:
7035:
5801:
5284:
5183:
4917:
4675:
4085:
3452:
2797:
2702:
2615:
1078:
958:
613:
61:
6913:"Integer priority queues with decrease key in constant time and the single source shortest paths problem"
3351:
2103:
7271:
3343:
3167:
3020:
2882:
113:
4624:
4129:
7012:
Exact
Solutions of Shortest-Path Problems Based on Mechanical Analogies: In Connection with Labyrinths
2170:
1775:
1603:
92:
7164:
7159:
7137:
6296:
5806:
5691:
5253:
4968:
4894:
3968:
in the graph. The all-pairs shortest paths problem for unweighted directed graphs was introduced by
1344:
1867:
7289:
7125:
7040:
5214:
4932:
4880:
4839:
4825:
4052:
2713:
2626:
1374:
1066:
483:
156:
109:
17:
5244:
is one that minimizes the travel time budget required to arrive on time with a given probability.
4735:
4684:
4633:
4547:
4435:
4367:
4304:
4251:
4139:
4007:
3688:
3514:
3426:
3296:
3145:
2999:
2861:
2776:
2681:
2594:
2518:
2443:
2297:
2015:
1925:
1835:
1743:
1658:
1578:
1502:
1427:
1285:
1229:
1173:
1130:
321:
7305:
7186:
6971:
6899:
6666:
6615:
6596:
6458:
6369:
6349:
6256:
6243:
6215:
6153:
5898:
5879:
5778:
5750:
5665:
5648:
5630:
5599:
5567:
5546:
5498:
5461:
5417:
5391:
5289:
1947:
1091:
solves the shortest stochastic path problem with an additional probabilistic weight on each node.
7261:
6760:
6752:
6260:
2468:
1452:
5081:
3319:
3026:
2805:
7208:
7149:
7016:
6832:
6764:
6627:
6587:
6546:
6414:
6314:
6233:
6000:
5975:
5950:
5906:
5871:
5768:
5525:
5484:
5409:
5350:
5193:
4391:
1687:
1088:
822:
6871:. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
2053:
789:
528:
288:
6981:
6947:
6924:
6889:
6855:
6814:
6791:
6708:
6650:
6605:
6573:
6515:
6485:
6448:
6406:
6361:
6337:
6292:
6272:
6225:
6188:
6143:
6135:
6093:
6066:
6039:
5944:
5863:
5760:
5726:
5699:
5622:
5451:
5401:
5325:
4928:
4835:" that try to find the shortest path in graphs like movie stars appearing in the same film.
4817:
4805:
3960:
The all-pairs shortest path problem finds the shortest paths between every pair of vertices
6993:
6722:
6662:
6529:
6284:
6202:
5319:
2546:
1530:
588:
561:
453:
426:
399:
261:
7112:
7099:
6989:
6739:
6718:
6658:
6525:
6497:
6470:
6428:
6390:
6280:
6198:
6172:
4956:
3824:
1118:
5240:
is one that maximizes the probability of arriving on time given a travel time budget. An
4810:
373:
5695:
693:
7103:
6831:. Algorithms and Combinatorics. Vol. 24. Springer. vol.A, sect.7.5b, p. 103.
6543:
Proceedings of the 27th
International Colloquium on Automata, Languages and Programming
6482:
Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983)
6304:
5822:
4955:(such problems are not believed to be efficiently solvable for large sets of data, see
4847:
2706:
1860:
1275:
860:
673:
653:
353:
7068:
7050:
6878:"Undirected single-source shortest paths with positive integer weights in linear time"
6796:
6779:
5669:
5146:
7318:
7203:
6903:
6713:
6679:
6630:(December 1981). "A priority queue in which initialization and queue operations take
6619:
6520:
6501:
6432:
6394:
6373:
6276:
6247:
6116:
5995:
Pouly, Marc; Kohlas, Jürg (2011). "Chapter 6. Valuation Algebras for Path Problems".
5905:. Rome (Italy), July 1966. Dunod (Paris); Gordon and Breach (New York). p. 271.
5782:
5133:
Cherkassky and Goldberg survey several other algorithms for negative cycle detection.
96:
Shortest path (A, C, E, D, F) between vertices A and F in the weighted directed graph
6670:
5634:
5421:
5256:, an algorithm that finds the shortest path between two vertices on a directed graph
3892:
For each edge (u, v) in the original graph, create two edges in the residual graph:
1069:
solves for single-pair shortest path using heuristics to try to speed up the search.
6462:
6157:
5764:
5465:
5264:
2041:
1082:
1057:
solves the single-source shortest path problem with only non-negative edge weights.
101:
6823:
Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225.
1405:
is the maximum length (or weight) among all edges, assuming integer edge weights.
7010:
6229:
5883:
5545:
Dürr, C.; Høyer, P. (1996-07-18). "A Quantum Algorithm for Finding the Minimum".
5344:
7154:
5279:
4996:
4960:
4952:
4798:
4790:
2619:
1768:
1219:
251:{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \cdots \times V}
149:
6929:
6912:
6120:
6043:
5747:
2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
1050:
Several well known algorithms exist for solving this problem and its variants.
6757:
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms
6560:
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997).
6300:
5730:
5703:
5591:
5329:
4905:
3949:
Repeat steps 2-4 until no more paths can be found from the source to the sink.
3903:
The residual graph represents the remaining capacity available in the network.
6410:
6097:
6070:
5910:
5875:
5830:
Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI)
5413:
3926:
Increase the flow on the edges of the shortest path by this minimum capacity.
6985:
6846:
Shimbel, Alfonso (1953). "Structural parameters of communication networks".
6437:"Fibonacci heaps and their uses in improved network optimization algorithms"
6382:
4935:
seeks a path so that the minimum label of any edge is as large as possible.
4876:
6578:
6561:
5796:
Bar-Noy, Amotz; Schieber, Baruch (1991). "The canadian traveller problem".
5440:"Algorithm 360: Shortest-Path Forest with Topological Ordering [H]"
4867:
done once and used for a large number of queries on the same road network.
3414:
harvnb error: no target: https://doi.org/10.1109/FOCS54457.2022.00064 (
3284:
harvnb error: no target: https://doi.org/10.1109/FOCS46700.2020.00090 (
3133:
harvnb error: no target: https://doi.org/10.1109/FOCS46700.2020.00018 (
6894:
6877:
6610:
6591:
6399:
Fibonacci heaps and their uses in improved network optimization algorithms
6328:
Dantzig, G. B. (January 1960). "On the Shortest Route through a Network".
5867:
5798:
Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms
5626:
5456:
5439:
1081:
solves all pairs shortest paths, and may be faster than Floyd–Warshall on
155:
Two vertices are adjacent when they are both incident to a common edge. A
6951:
6818:
6489:
6341:
6212:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
6193:
6176:
5551:
5396:
5179:
4843:
4794:
2987:
harvnb error: no target: https://doi.org/10.1137/1.9781611974782.48 (
1030:, in which we have to find shortest paths between every pair of vertices
160:
6453:
6436:
6148:
6139:
5851:
4938:
Other related problems may be classified into the following categories.
6859:
6654:
6365:
5062:, which gives the computers an incentive to reveal their true weights.
6307:(2001) . "Single-Source Shortest Paths and All-Pairs Shortest Paths".
5653:"Highway Dimension, Shortest Paths, and Provably Efficient Algorithms"
5405:
6780:"A new approach to all-pairs shortest paths on real-weighted graphs"
5138:
General algebraic framework on semirings: the algebraic path problem
6220:
5755:
6976:
6962:(2014). "Faster all-pairs shortest paths via circuit complexity".
5823:"Route planning under uncertainty: the Canadian traveller problem"
5572:
5346:
Graph Theory with Applications to Engineering and Computer Science
5294:
4801:. For this application fast specialized algorithms are available.
91:
5655:. ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.
4340:
applied to every vertex (requires constant-time multiplication).
3410:
3280:
3129:
1095:
Additional algorithms and associated evaluations may be found in
1063:
solves the single-source problem if edge weights may be negative.
7218:
7142:
6402:
3666:
Finds a negative cycle or calculates distances to all vertices.
7072:
6261:"Shortest paths algorithms: theory and experimental evaluation"
3615:
harvnb error: no target: https://arxiv.org/abs/2311.02520 (
2983:
1008:, in which we have to find shortest paths from a source vertex
5141:
4990:
3625:
3505:
2420:
Directed graphs with arbitrary weights without negative cycles
2383:
29:
7056:(Report). Project Rand. United States Air Force. RM-5433-PR.
6313:(2nd ed.). MIT Press and McGraw-Hill. pp. 580–642.
6592:"Efficient algorithms for shortest paths in sparse networks"
6401:. 25th Annual Symposium on Foundations of Computer Science.
5997:
Generic Inference: A Unifying Theory for Automated Reasoning
5672:. Symposium on Experimental Algorithms, pages 230–241, 2011.
3852:
993:, this is equivalent to finding the path with fewest edges.
7198:
7181:
6541:. In Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (eds.).
6352:(1959). "A note on two problems in connexion with graphs".
3662:
Directed graphs with arbitrary weights with negative cycles
5369:
1377:
can solve the single-source shortest path problem in time
6753:"Computing shortest paths with comparisons and additions"
6746:. Cambridge: Harvard University Press. pp. 285–292.
5903:
Théorie des graphes (journées internationales d'études)
5850:
Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01).
3271:{\displaystyle O((E+V^{3/2})\log ^{O(1)}V\log ^{O(1)}L)}
2288:
1722:
1096:
6867:
Shimbel, A. (1955). "Structure in communication nets".
5972:
Graphs, Dioids and Semirings: New Models and Algorithms
5158:
3642:
2400:
5943:
Baras, John; Theodorakopoulos, George (4 April 2010).
3939:
Update the residual graph based on the augmented flow.
6829:
Combinatorial Optimization — Polyhedra and Efficiency
5970:
Gondran, Michel; Minoux, Michel (2008). "chapter 4".
5084:
4738:
4687:
4636:
4574:
4550:
4461:
4438:
4394:
4370:
4307:
4254:
4165:
4142:
4088:
4055:
4010:
3827:
3792:
3716:
3691:
3611:
3543:
3517:
3455:
3429:
3354:
3322:
3299:
3178:
3148:
3058:
3029:
3002:
2974:{\displaystyle O(E^{10/7}\log ^{O(1)}V\log ^{O(1)}L)}
2893:
2864:
2808:
2779:
2716:
2684:
2629:
2597:
2549:
2521:
2471:
2446:
2326:
2300:
2242:
2173:
2106:
2056:
2018:
1958:
1928:
1870:
1838:
1778:
1746:
1690:
1661:
1606:
1581:
1533:
1505:
1455:
1430:
1288:
1232:
1176:
1133:
961:
883:
863:
825:
792:
721:
696:
676:
656:
622:
591:
564:
531:
486:
456:
429:
402:
376:
356:
324:
291:
264:
169:
6869:
Proceedings of the Symposium on Information Networks
6385:(Report). Santa Monica, CA: RAND Corporation. P-923.
7270:
7227:
7111:
6562:"Faster Shortest-Path Algorithms for Planar Graphs"
5200:
Shortest path in stochastic time-dependent networks
1000:, to distinguish it from the following variations:
7032:Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms
6441:Journal of the Association for Computing Machinery
6115:Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James;
5122:
4746:
4695:
4644:
4614:
4558:
4529:{\displaystyle O(V^{3}/2^{\Omega (\log V)^{1/2}})}
4528:
4446:
4416:
4378:
4315:
4295:
4262:
4233:{\displaystyle O(V^{3}/2^{\Omega (\log V)^{1/2}})}
4232:
4150:
4119:
4073:
4018:
3923:Find the minimum capacity along the shortest path.
3842:
3810:
3749:
3699:
3601:
3525:
3495:
3437:
3400:
3335:
3307:
3270:
3156:
3119:
3042:
3010:
2973:
2872:
2838:
2787:
2749:
2692:
2662:
2605:
2567:
2529:
2499:
2454:
2366:
2308:
2278:
2212:
2140:
2080:
2026:
1998:
1936:
1902:
1846:
1816:
1754:
1712:
1669:
1639:
1589:
1551:
1513:
1483:
1438:
1296:
1240:
1184:
1141:
985:
947:
869:
849:
811:
778:
707:
682:
662:
642:
604:
577:
550:
517:
469:
442:
415:
388:
362:
342:
310:
277:
250:
6121:"Faster algorithms for the shortest path problem"
5949:. Morgan & Claypool Publishers. pp. 9–.
4831:A more lighthearted application is the games of "
1389:in arbitrarily-weighted directed acyclic graphs.
6734:. Cleveland, Ohio: Case Institute of Technology.
6678:Karlsson, Rolf G.; Poblete, Patricio V. (1983).
1730:
5078:can be used to detect a negative cycle in time
2154:
955:When each edge in the graph has unit weight or
5297:(TRansparent Interconnection of Lots of Links)
5205:is a stochastic time-dependent (STD) network.
1734:
948:{\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}
7084:
7051:An Appraisal of Some Shortest Path Algorithms
6086:International Journal of Operational Research
6059:International Journal of Operational Research
2763:
2759:
1916:
1912:
1271:
779:{\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}
136:The shortest path problem can be defined for
8:
6742:(1959). "The shortest path through a maze".
5924:Derniame, Jean Claude; Pair, Claude (1971).
4068:
4056:
3506:Bernstein, Nanongkai & Wulff-Nilsen 2022
3346:with dynamic min-ratio cycle data structure
980:
974:
512:
493:
6751:Pettie, Seth; Ramachandran, Vijaya (2002).
5025:. Unsourced material may be challenged and
1999:{\displaystyle O({\sqrt {VE}}\log ^{2}{V})}
643:{\displaystyle f:E\rightarrow \mathbb {R} }
7091:
7077:
7069:
7039:
6975:
6928:
6893:
6795:
6712:
6609:
6577:
6539:"Improved Shortest Paths on the Word RAM"
6519:
6502:"Scaling algorithms for network problems"
6475:"Scaling algorithms for network problems"
6452:
6219:
6192:
6147:
5974:. Springer Science & Business Media.
5926:Problèmes de cheminement dans les graphes
5805:
5754:
5571:
5550:
5455:
5395:
5112:
5104:
5099:
5091:
5083:
5045:Learn how and when to remove this message
4740:
4739:
4737:
4689:
4688:
4686:
4638:
4637:
4635:
4604:
4595:
4585:
4573:
4552:
4551:
4549:
4511:
4507:
4487:
4478:
4472:
4460:
4440:
4439:
4437:
4405:
4393:
4372:
4371:
4369:
4309:
4308:
4306:
4256:
4255:
4253:
4215:
4211:
4191:
4182:
4176:
4164:
4144:
4143:
4141:
4099:
4087:
4054:
4012:
4011:
4009:
3826:
3799:
3795:
3794:
3791:
3739:
3726:
3715:
3693:
3692:
3690:
3575:
3561:
3557:
3542:
3519:
3518:
3516:
3469:
3454:
3431:
3430:
3428:
3365:
3353:
3327:
3321:
3301:
3300:
3298:
3244:
3219:
3202:
3198:
3177:
3150:
3149:
3147:
3120:{\displaystyle E^{4/3+o(1)}\log ^{O(1)}L}
3096:
3067:
3063:
3057:
3034:
3028:
3004:
3003:
3001:
2947:
2922:
2908:
2904:
2892:
2866:
2865:
2863:
2807:
2781:
2780:
2778:
2715:
2686:
2685:
2683:
2628:
2599:
2598:
2596:
2548:
2523:
2522:
2520:
2482:
2470:
2448:
2447:
2445:
2355:
2348:
2325:
2302:
2301:
2299:
2266:
2258:
2241:
2191:
2187:
2172:
2129:
2122:
2105:
2055:
2020:
2019:
2017:
1988:
1979:
1965:
1957:
1930:
1929:
1927:
1892:
1869:
1840:
1839:
1837:
1806:
1777:
1748:
1747:
1745:
1701:
1689:
1663:
1662:
1660:
1629:
1617:
1605:
1583:
1582:
1580:
1532:
1507:
1506:
1504:
1466:
1454:
1432:
1431:
1429:
1398:
1290:
1289:
1287:
1234:
1233:
1231:
1178:
1177:
1175:
1135:
1134:
1132:
996:The problem is also sometimes called the
960:
921:
899:
888:
882:
862:
830:
824:
797:
791:
767:
748:
735:
720:
695:
675:
655:
636:
635:
621:
596:
590:
569:
563:
536:
530:
500:
485:
461:
455:
434:
428:
407:
401:
375:
355:
323:
296:
290:
269:
263:
215:
196:
183:
168:
80:Learn how and when to remove this message
5433:
5431:
4538:
4350:
4242:
3990:
3769:
3668:
3602:{\displaystyle O(EV^{8/9}\log ^{O(1)}V)}
2423:
2279:{\displaystyle O(E+V{\sqrt {\log {L}}})}
1726:
1407:
1393:Directed graphs with nonnegative weights
1329:
1319:(requires constant-time multiplication)
1164:
1111:
1097:Cherkassky, Goldberg & Radzik (1996)
1017:single-destination shortest path problem
43:This article includes a list of general
7063:from the original on November 17, 2015.
6917:Journal of Computer and System Sciences
6566:Journal of Computer and System Sciences
6507:Journal of Computer and System Sciences
5311:
4776:
3969:
3750:{\displaystyle O(E{\sqrt {V}}\log {N})}
2852:
2767:
2672:
2581:
2577:
2150:
1826:
1649:
1565:
1561:
1215:
124:of its constituent edges is minimized.
7340:Computational problems in graph theory
5496:
4726:
4615:{\displaystyle O(V^{2.5}\log ^{2}{V})}
4337:
3766:Planar graphs with nonnegative weights
2376:
1316:
5852:"Negative-cycle detection algorithms"
4842:, include plant and facility layout,
4838:Other applications, often studied in
4804:If one represents a nondeterministic
3811:{\displaystyle \mathbb {R} _{\geq 0}}
2585:
2367:{\displaystyle O(E+V\log {\log {V}})}
2226:
2222:
1569:
27:Computational problem of graph theory
7:
5821:Nikolova, Evdokia; Karger, David R.
5518:Kleinberg, Jon; Tardos, Éva (2005).
5023:adding citations to reliable sources
4120:{\displaystyle O(V^{\omega }\log V)}
3496:{\displaystyle O(E\log ^{8}V\log L)}
3447:Based on low-diameter decomposition
2848:
2509:
2090:
1493:
986:{\displaystyle f:E\rightarrow \{1\}}
6970:. New York: ACM. pp. 664–673.
6964:Proceedings of the 46th Annual ACM
6848:Bulletin of Mathematical Biophysics
5719:Computers & Operations Research
5479:Cormen, Thomas H. (July 31, 2009).
3401:{\displaystyle O(E^{1+o(1)}\log L)}
2141:{\displaystyle O(E\log {\log {L}})}
1012:to all other vertices in the graph.
1006:single-source shortest path problem
650:, and an undirected (simple) graph
18:Single source shortest path problem
4488:
4192:
4065:
1397:The following table is taken from
49:it lacks sufficient corresponding
25:
7034:. Atlanta, GA. pp. 212–221.
5664:Abraham, Ittai; Delling, Daniel;
998:single-pair shortest path problem
6966:Symposium on Theory of Computing
6778:Pettie, Seth (26 January 2004).
6181:Quarterly of Applied Mathematics
6167:from the original on 2022-10-09.
6032:Expert Systems with Applications
5839:from the original on 2022-10-09.
5602:from the original on 2021-12-11.
5524:(1st ed.). Addison-Wesley.
5343:Deo, Narsingh (17 August 2016).
5145:
4995:
4971:in a graph is also NP-complete.
3629:
2387:
2213:{\displaystyle O(E\log _{E/V}L)}
1817:{\displaystyle O((E+V)\log {V})}
1640:{\displaystyle O(V^{2}\log {V})}
1075:solves all pairs shortest paths.
34:
7306:List of graph search algorithms
7049:Dreyfus, S. E. (October 1967).
7015:. Amazon Digital Services LLC.
5684:Computer Physics Communications
4949:Constrained Shortest Path First
3130:Axiotis, Mądry & Vladu 2020
1028:all-pairs shortest path problem
6940:Operational Research Quarterly
5765:10.1109/IROS40897.2019.8968113
5349:. Courier Dover Publications.
5275:Min-plus matrix multiplication
5117:
5113:
5105:
5100:
5092:
5088:
5060:a variant of the VCG mechanism
4916:For shortest path problems in
4609:
4578:
4523:
4504:
4491:
4465:
4411:
4398:
4296:Pettie & Ramachandran 2002
4227:
4208:
4195:
4169:
4114:
4092:
3837:
3831:
3744:
3720:
3596:
3585:
3579:
3547:
3490:
3459:
3395:
3381:
3375:
3358:
3265:
3254:
3248:
3229:
3223:
3212:
3185:
3182:
3106:
3100:
3087:
3081:
2968:
2957:
2951:
2932:
2926:
2897:
2833:
2830:
2818:
2812:
2744:
2720:
2657:
2633:
2562:
2553:
2494:
2475:
2361:
2330:
2273:
2246:
2207:
2177:
2135:
2110:
2075:
2060:
1993:
1962:
1903:{\displaystyle O(E+V\log {V})}
1897:
1874:
1811:
1797:
1785:
1782:
1707:
1694:
1634:
1610:
1546:
1537:
1478:
1459:
971:
939:
914:
773:
728:
632:
221:
176:
1:
6827:Schrijver, Alexander (2004).
6797:10.1016/s0304-3975(03)00402-x
6695:algorithm for shortest paths"
5503:: CS1 maint: date and year (
4074:{\displaystyle \{1,\infty \}}
2750:{\displaystyle O(VE+V\log V)}
2663:{\displaystyle O(VE+V\log V)}
558:is the edge incident to both
518:{\displaystyle E=\{e_{i,j}\}}
6784:Theoretical Computer Science
6714:10.1016/0166-218X(83)90104-X
6700:Discrete Applied Mathematics
6521:10.1016/0022-0000(85)90039-X
6277:10.1016/0025-5610(95)00021-6
6230:10.1109/focs54457.2022.00063
5647:Abraham, Ittai; Fiat, Amos;
4747:{\displaystyle \mathbb {N} }
4696:{\displaystyle \mathbb {R} }
4645:{\displaystyle \mathbb {R} }
4559:{\displaystyle \mathbb {R} }
4447:{\displaystyle \mathbb {N} }
4379:{\displaystyle \mathbb {R} }
4316:{\displaystyle \mathbb {N} }
4263:{\displaystyle \mathbb {R} }
4151:{\displaystyle \mathbb {N} }
4019:{\displaystyle \mathbb {R} }
3895:(u, v) with capacity c(u, v)
3700:{\displaystyle \mathbb {Z} }
3526:{\displaystyle \mathbb {R} }
3438:{\displaystyle \mathbb {Z} }
3308:{\displaystyle \mathbb {Z} }
3157:{\displaystyle \mathbb {Z} }
3011:{\displaystyle \mathbb {Z} }
2873:{\displaystyle \mathbb {Z} }
2788:{\displaystyle \mathbb {Z} }
2693:{\displaystyle \mathbb {R} }
2606:{\displaystyle \mathbb {R} }
2530:{\displaystyle \mathbb {R} }
2455:{\displaystyle \mathbb {R} }
2309:{\displaystyle \mathbb {N} }
2027:{\displaystyle \mathbb {N} }
1937:{\displaystyle \mathbb {R} }
1847:{\displaystyle \mathbb {R} }
1755:{\displaystyle \mathbb {R} }
1731:Pollack & Wiebenson 1960
1670:{\displaystyle \mathbb {R} }
1590:{\displaystyle \mathbb {R} }
1514:{\displaystyle \mathbb {R} }
1439:{\displaystyle \mathbb {R} }
1297:{\displaystyle \mathbb {N} }
1241:{\displaystyle \mathbb {R} }
1185:{\displaystyle \mathbb {R} }
1142:{\displaystyle \mathbb {R} }
1103:Single-source shortest paths
343:{\displaystyle 1\leq i<n}
159:in an undirected graph is a
108:is the problem of finding a
6643:Mathematical Systems Theory
5483:(3rd ed.). MIT Press.
3535:Hop-limited shortest paths
2800:applied to Dial's algorithm
2155:Karlsson & Poblete 1983
370:is called a path of length
7361:
6930:10.1016/j.jcss.2004.04.003
6310:Introduction to Algorithms
6214:. IEEE. pp. 600–611.
6044:10.1016/j.eswa.2015.02.046
5481:Introduction to Algorithms
4981:Canadian traveller problem
4965:Traveling Salesman Problem
4809:states of a puzzle like a
3935:Update the Residual Graph:
2500:{\displaystyle O(V^{2}EL)}
1735:Whiting & Hillier 1960
1484:{\displaystyle O(V^{2}EL)}
7303:
7009:Altıntaş, Gökhan (2020).
6429:Fredman, Michael Lawrence
6391:Fredman, Michael Lawrence
6259:; Radzik, Tomasz (1996).
5999:. John Wiley & Sons.
5946:Path Problems in Networks
5731:10.1016/j.cor.2012.07.008
5704:10.1016/j.cpc.2005.01.020
5444:Communications of the ACM
5384:SIAM Journal on Computing
5330:10.1007/978-3-031-02574-7
5321:The Shortest-Path Problem
5123:{\displaystyle O(|V||E|)}
4833:six degrees of separation
3336:{\displaystyle \ell _{1}}
3281:van den Brand et al. 2020
3043:{\displaystyle \ell _{p}}
2839:{\displaystyle O(V(E+L))}
2764:Fredman & Tarjan 1987
2760:Fredman & Tarjan 1984
1917:Fredman & Tarjan 1987
1913:Fredman & Tarjan 1984
1272:Fredman & Tarjan 1984
857:) that over all possible
670:, the shortest path from
120:such that the sum of the
7335:Polynomial-time problems
6537:Hagerup, Torben (2000).
6411:10.1109/SFCS.1984.715934
6265:Mathematical Programming
6098:10.1504/IJOR.2014.064541
6071:10.1504/IJOR.2014.064020
5856:Mathematical Programming
5438:Dial, Robert B. (1969).
5066:Negative cycle detection
4987:Strategic shortest paths
4969:finding the longest path
4768: log log
4718: log log
4427:Floyd–Warshall algorithm
4417:{\displaystyle O(V^{3})}
4132:(expected running time)
4044:Floyd–Warshall algorithm
3956:All-pairs shortest paths
3888:Create a Residual Graph:
1713:{\displaystyle O(V^{2})}
1073:Floyd–Warshall algorithm
850:{\displaystyle v_{n}=v'}
7214:Monte Carlo tree search
6986:10.1145/2591796.2591811
6911:Thorup, Mikkel (2004).
6876:Thorup, Mikkel (1999).
5930:Path Problems in Graphs
5270:K shortest path routing
5260:Euclidean shortest path
5231:travel time variability
5227:travel time reliability
5223:stochastic optimization
4922:Euclidean shortest path
4890:Contraction hierarchies
3909:Find the Shortest Path:
2081:{\displaystyle O(E+LV)}
1369:Directed acyclic graphs
812:{\displaystyle v_{1}=v}
551:{\displaystyle e_{i,j}}
311:{\displaystyle v_{i+1}}
64:more precise citations.
6579:10.1006/jcss.1997.1493
6255:Cherkassky, Boris V.;
6177:"On a routing problem"
5749:. pp. 3519–3525.
5285:Shortest Path Bridging
5184:algebraic path problem
5124:
5076:Bellman–Ford algorithm
4942:Paths with constraints
4918:computational geometry
4748:
4697:
4646:
4616:
4560:
4530:
4448:
4418:
4380:
4317:
4264:
4234:
4152:
4121:
4075:
4020:
3898:(v, u) with capacity 0
3873:Shortest Path Problems
3844:
3812:
3751:
3701:
3603:
3527:
3497:
3439:
3402:
3337:
3309:
3272:
3158:
3121:
3044:
3012:
2975:
2885:with Laplacian solver
2874:
2840:
2789:
2751:
2694:
2664:
2607:
2569:
2540:Bellman–Ford algorithm
2531:
2501:
2456:
2368:
2310:
2280:
2214:
2142:
2082:
2028:
2000:
1938:
1904:
1848:
1818:
1756:
1714:
1671:
1641:
1591:
1553:
1524:Bellman–Ford algorithm
1515:
1485:
1440:
1298:
1242:
1186:
1143:
1061:Bellman–Ford algorithm
987:
949:
910:
871:
851:
813:
780:
709:
684:
664:
644:
606:
579:
552:
519:
471:
444:
417:
390:
364:
344:
312:
279:
252:
97:
7272:Minimum spanning tree
6895:10.1145/316542.316548
6611:10.1145/321992.321993
6354:Numerische Mathematik
6297:Leiserson, Charles E.
5932:]. Dunod (Paris).
5868:10.1007/s101070050058
5668:; Werneck, Renato F.
5651:; Werneck, Renato F.
5627:10.1145/242224.242246
5615:ACM Computing Surveys
5592:"Fast route planning"
5457:10.1145/363269.363610
5125:
4975:Partial observability
4749:
4698:
4647:
4617:
4561:
4531:
4449:
4419:
4381:
4318:
4265:
4235:
4153:
4122:
4076:
4021:
3853:Henzinger et al. 1997
3845:
3813:
3752:
3702:
3604:
3528:
3498:
3440:
3403:
3344:interior-point method
3338:
3310:
3273:
3168:interior-point method
3159:
3122:
3045:
3021:Interior-point method
3013:
2976:
2883:Interior-point method
2875:
2841:
2790:
2752:
2695:
2665:
2608:
2570:
2568:{\displaystyle O(VE)}
2532:
2502:
2457:
2369:
2311:
2281:
2215:
2143:
2083:
2029:
2001:
1939:
1905:
1849:
1819:
1757:
1715:
1672:
1642:
1592:
1554:
1552:{\displaystyle O(VE)}
1516:
1486:
1441:
1299:
1243:
1187:
1144:
988:
950:
884:
872:
852:
814:
781:
710:
685:
665:
645:
607:
605:{\displaystyle v_{j}}
580:
578:{\displaystyle v_{i}}
553:
520:
472:
470:{\displaystyle v_{i}}
445:
443:{\displaystyle v_{n}}
418:
416:{\displaystyle v_{1}}
391:
365:
345:
313:
280:
278:{\displaystyle v_{i}}
253:
106:shortest path problem
95:
7257:Shortest path faster
7165:Breadth-first search
7160:Bidirectional search
7106:traversal algorithms
6952:10.1057/jors.1960.32
6819:10.1287/opre.8.2.224
6490:10.1109/SFCS.1983.68
6484:. pp. 248–258.
6405:. pp. 338–346.
6381:Ford, L. R. (1956).
6342:10.1287/mnsc.6.2.187
5832:. pp. 969–974.
5254:Bidirectional search
5221:. These methods use
5219:Dijkstra's algorithm
5082:
5019:improve this section
4895:Transit node routing
4736:
4703:(no negative cycles)
4685:
4652:(no negative cycles)
4634:
4572:
4566:(no negative cycles)
4548:
4459:
4436:
4392:
4386:(no negative cycles)
4368:
4305:
4252:
4163:
4140:
4086:
4053:
4008:
3880:Transformation Steps
3843:{\displaystyle O(V)}
3825:
3790:
3714:
3689:
3643:adding missing items
3541:
3515:
3453:
3427:
3352:
3320:
3297:
3176:
3146:
3056:
3027:
3000:
2891:
2862:
2806:
2777:
2714:
2682:
2627:
2595:
2547:
2519:
2469:
2444:
2401:adding missing items
2324:
2298:
2240:
2171:
2104:
2054:
2038:Dijkstra's algorithm
2016:
1956:
1926:
1868:
1857:Dijkstra's algorithm
1836:
1776:
1765:Dijkstra's algorithm
1744:
1723:Leyzorek et al. 1957
1688:
1680:Dijkstra's algorithm
1659:
1604:
1579:
1531:
1503:
1453:
1428:
1345:Breadth-first search
1286:
1230:
1174:
1131:
1055:Dijkstra's algorithm
959:
881:
861:
823:
790:
719:
694:
674:
654:
620:
589:
562:
529:
484:
454:
427:
400:
374:
354:
322:
289:
262:
167:
7192:Iterative deepening
6454:10.1145/28869.28874
6383:Network Flow Theory
6257:Goldberg, Andrew V.
6140:10.1145/77600.77615
6134:(2). ACM: 213–223.
5696:2005CoPhC.168..209K
5666:Goldberg, Andrew V.
5649:Goldberg, Andrew V.
5621:(4es). Article 18.
5215:dynamic programming
4933:widest path problem
4899:Reach-based pruning
4881:triangle inequality
4840:operations research
4826:widest path problem
3759:Andrew V. Goldberg
2798:Johnson's technique
1950:with adjacency list
1375:topological sorting
1373:An algorithm using
1079:Johnson's algorithm
1067:A* search algorithm
389:{\displaystyle n-1}
7345:Edsger W. Dijkstra
7187:Depth-first search
6882:Journal of the ACM
6860:10.1007/BF02476438
6655:10.1007/BF01786986
6628:Johnson, Donald B.
6597:Journal of the ACM
6588:Johnson, Donald B.
6545:. pp. 61–72.
6366:10.1007/BF01386390
6330:Management Science
6194:10.1090/qam/102435
6128:Journal of the ACM
5899:Rosentiehl, Pierre
5590:(March 23, 2009).
5370:Cormen et al. 2001
5290:Shortest path tree
5238:most reliable path
5194:valuation algebras
5157:. You can help by
5120:
4822:telecommunications
4744:
4693:
4642:
4612:
4556:
4526:
4444:
4414:
4376:
4313:
4260:
4230:
4148:
4130:Seidel's algorithm
4117:
4071:
4016:
3840:
3808:
3747:
3697:
3641:; you can help by
3599:
3523:
3493:
3435:
3398:
3333:
3305:
3268:
3154:
3117:
3040:
3008:
2971:
2870:
2836:
2785:
2747:
2690:
2660:
2603:
2565:
2527:
2497:
2452:
2399:; you can help by
2364:
2306:
2276:
2210:
2138:
2078:
2036:Dial's algorithm (
2024:
1996:
1948:Dijkstra algorithm
1934:
1900:
1844:
1814:
1752:
1710:
1667:
1637:
1587:
1549:
1511:
1481:
1436:
1294:
1238:
1182:
1139:
983:
945:
877:minimizes the sum
867:
847:
809:
776:
708:{\displaystyle v'}
705:
680:
660:
640:
602:
575:
548:
515:
467:
440:
413:
386:
360:
340:
308:
275:
248:
98:
7312:
7311:
7209:Jump point search
7150:Best-first search
6838:978-3-540-20456-5
6770:978-0-89871-513-2
6552:978-3-540-67715-4
6433:Tarjan, Robert E.
6395:Tarjan, Robert E.
6301:Rivest, Ronald L.
6293:Cormen, Thomas H.
6239:978-1-6654-5519-0
6117:Tarjan, Robert E.
6038:(12): 5056–5064.
6006:978-1-118-01086-0
5981:978-0-387-75450-5
5956:978-1-59829-924-3
5774:978-1-7281-4004-9
5406:10.1137/050644719
5356:978-0-486-80793-5
5175:
5174:
5055:
5054:
5047:
4879:, landmarks, and
4782:
4781:
4344:
4343:
4283: log α(
3919:Augment the Flow:
3858:
3857:
3763:
3762:
3731:
3659:
3658:
3624:
3623:
2984:Cohen et al. 2017
2417:
2416:
2382:
2381:
2289:Ahuja et al. 1990
2271:
2164:Gabow's algorithm
2008:Dürr et al. 2006
1973:
1366:
1365:
1326:Unweighted graphs
1323:
1322:
1108:Undirected graphs
1089:Viterbi algorithm
870:{\displaystyle n}
683:{\displaystyle v}
663:{\displaystyle G}
363:{\displaystyle P}
90:
89:
82:
16:(Redirected from
7352:
7093:
7086:
7079:
7070:
7064:
7062:
7055:
7045:
7043:
7026:
6997:
6979:
6955:
6934:
6932:
6907:
6897:
6872:
6863:
6842:
6822:
6801:
6799:
6774:
6747:
6735:
6726:
6716:
6694:
6674:
6640:
6623:
6613:
6583:
6581:
6556:
6533:
6523:
6498:Gabow, Harold N.
6493:
6479:
6466:
6456:
6424:
6386:
6377:
6345:
6324:
6288:
6251:
6223:
6206:
6196:
6173:Bellman, Richard
6168:
6166:
6151:
6125:
6102:
6101:
6081:
6075:
6074:
6054:
6048:
6047:
6026:
6020:
6017:
6011:
6010:
5992:
5986:
5985:
5967:
5961:
5960:
5940:
5934:
5933:
5921:
5915:
5914:
5894:
5888:
5887:
5847:
5841:
5840:
5838:
5827:
5818:
5812:
5811:
5809:
5807:10.1.1.1088.3015
5793:
5787:
5786:
5758:
5741:
5735:
5734:
5714:
5708:
5707:
5679:
5673:
5662:
5656:
5645:
5639:
5638:
5610:
5604:
5603:
5596:Google Tech Talk
5584:
5578:
5577:
5575:
5563:
5557:
5556:
5554:
5552:quant-ph/9607014
5542:
5536:
5535:
5521:Algorithm Design
5515:
5509:
5508:
5502:
5494:
5476:
5470:
5469:
5459:
5435:
5426:
5425:
5399:
5397:quant-ph/0401091
5390:(6): 1310–1328.
5379:
5373:
5367:
5361:
5360:
5340:
5334:
5333:
5316:
5170:
5167:
5149:
5142:
5129:
5127:
5126:
5121:
5116:
5108:
5103:
5095:
5050:
5043:
5039:
5036:
5030:
4999:
4991:
4929:Reptation theory
4912:Related problems
4806:abstract machine
4773:
4753:
4751:
4750:
4745:
4743:
4723:
4702:
4700:
4699:
4694:
4692:
4676:Johnson–Dijkstra
4672:
4651:
4649:
4648:
4643:
4641:
4621:
4619:
4618:
4613:
4608:
4600:
4599:
4590:
4589:
4565:
4563:
4562:
4557:
4555:
4535:
4533:
4532:
4527:
4522:
4521:
4520:
4519:
4515:
4482:
4477:
4476:
4453:
4451:
4450:
4445:
4443:
4423:
4421:
4420:
4415:
4410:
4409:
4385:
4383:
4382:
4377:
4375:
4351:
4334:
4322:
4320:
4319:
4314:
4312:
4292:
4269:
4267:
4266:
4261:
4259:
4239:
4237:
4236:
4231:
4226:
4225:
4224:
4223:
4219:
4186:
4181:
4180:
4157:
4155:
4154:
4149:
4147:
4126:
4124:
4123:
4118:
4104:
4103:
4080:
4078:
4077:
4072:
4040:
4025:
4023:
4022:
4017:
4015:
3991:
3987:Undirected graph
3982:
3967:
3963:
3849:
3847:
3846:
3841:
3817:
3815:
3814:
3809:
3807:
3806:
3798:
3770:
3756:
3754:
3753:
3748:
3743:
3732:
3727:
3706:
3704:
3703:
3698:
3696:
3669:
3654:
3651:
3633:
3632:
3626:
3620:
3608:
3606:
3605:
3600:
3589:
3588:
3570:
3569:
3565:
3532:
3530:
3529:
3524:
3522:
3502:
3500:
3499:
3494:
3474:
3473:
3444:
3442:
3441:
3436:
3434:
3419:
3411:Chen et al. 2022
3407:
3405:
3404:
3399:
3385:
3384:
3342:
3340:
3339:
3334:
3332:
3331:
3314:
3312:
3311:
3306:
3304:
3289:
3277:
3275:
3274:
3269:
3258:
3257:
3233:
3232:
3211:
3210:
3206:
3163:
3161:
3160:
3155:
3153:
3138:
3126:
3124:
3123:
3118:
3110:
3109:
3091:
3090:
3071:
3049:
3047:
3046:
3041:
3039:
3038:
3017:
3015:
3014:
3009:
3007:
2992:
2980:
2978:
2977:
2972:
2961:
2960:
2936:
2935:
2917:
2916:
2912:
2879:
2877:
2876:
2871:
2869:
2851:, adapted after
2845:
2843:
2842:
2837:
2794:
2792:
2791:
2786:
2784:
2766:, adapted after
2756:
2754:
2753:
2748:
2703:Johnson-Dijkstra
2699:
2697:
2696:
2691:
2689:
2669:
2667:
2666:
2661:
2616:Johnson-Dijkstra
2612:
2610:
2609:
2604:
2602:
2574:
2572:
2571:
2566:
2536:
2534:
2533:
2528:
2526:
2506:
2504:
2503:
2498:
2487:
2486:
2461:
2459:
2458:
2453:
2451:
2424:
2412:
2409:
2391:
2390:
2384:
2373:
2371:
2370:
2365:
2360:
2359:
2315:
2313:
2312:
2307:
2305:
2285:
2283:
2282:
2277:
2272:
2270:
2259:
2219:
2217:
2216:
2211:
2200:
2199:
2195:
2147:
2145:
2144:
2139:
2134:
2133:
2087:
2085:
2084:
2079:
2033:
2031:
2030:
2025:
2023:
2005:
2003:
2002:
1997:
1992:
1984:
1983:
1974:
1966:
1943:
1941:
1940:
1935:
1933:
1909:
1907:
1906:
1901:
1896:
1853:
1851:
1850:
1845:
1843:
1823:
1821:
1820:
1815:
1810:
1761:
1759:
1758:
1753:
1751:
1719:
1717:
1716:
1711:
1706:
1705:
1676:
1674:
1673:
1668:
1666:
1646:
1644:
1643:
1638:
1633:
1622:
1621:
1596:
1594:
1593:
1588:
1586:
1558:
1556:
1555:
1550:
1520:
1518:
1517:
1512:
1510:
1490:
1488:
1487:
1482:
1471:
1470:
1445:
1443:
1442:
1437:
1435:
1408:
1399:Schrijver (2004)
1388:
1330:
1303:
1301:
1300:
1295:
1293:
1247:
1245:
1244:
1239:
1237:
1208:) log
1191:
1189:
1188:
1183:
1181:
1148:
1146:
1145:
1140:
1138:
1112:
992:
990:
989:
984:
954:
952:
951:
946:
938:
937:
909:
898:
876:
874:
873:
868:
856:
854:
853:
848:
846:
835:
834:
818:
816:
815:
810:
802:
801:
785:
783:
782:
777:
772:
771:
753:
752:
740:
739:
714:
712:
711:
706:
704:
689:
687:
686:
681:
669:
667:
666:
661:
649:
647:
646:
641:
639:
616:weight function
611:
609:
608:
603:
601:
600:
584:
582:
581:
576:
574:
573:
557:
555:
554:
549:
547:
546:
524:
522:
521:
516:
511:
510:
476:
474:
473:
468:
466:
465:
449:
447:
446:
441:
439:
438:
422:
420:
419:
414:
412:
411:
395:
393:
392:
387:
369:
367:
366:
361:
349:
347:
346:
341:
317:
315:
314:
309:
307:
306:
284:
282:
281:
276:
274:
273:
257:
255:
254:
249:
220:
219:
201:
200:
188:
187:
116:(or nodes) in a
85:
78:
74:
71:
65:
60:this article by
51:inline citations
38:
37:
30:
21:
7360:
7359:
7355:
7354:
7353:
7351:
7350:
7349:
7315:
7314:
7313:
7308:
7299:
7266:
7223:
7107:
7097:
7065:DTIC AD-661265.
7060:
7053:
7048:
7029:
7023:
7008:
7005:
7003:Further reading
7000:
6958:
6937:
6910:
6875:
6866:
6845:
6839:
6826:
6804:
6777:
6771:
6750:
6738:
6729:
6681:
6677:
6631:
6626:
6586:
6559:
6553:
6536:
6496:
6477:
6469:
6427:
6421:
6389:
6380:
6350:Dijkstra, E. W.
6348:
6327:
6321:
6305:Stein, Clifford
6291:
6254:
6240:
6209:
6171:
6164:
6123:
6114:
6110:
6105:
6083:
6082:
6078:
6056:
6055:
6051:
6028:
6027:
6023:
6018:
6014:
6007:
5994:
5993:
5989:
5982:
5969:
5968:
5964:
5957:
5942:
5941:
5937:
5923:
5922:
5918:
5896:
5895:
5891:
5849:
5848:
5844:
5836:
5825:
5820:
5819:
5815:
5795:
5794:
5790:
5775:
5743:
5742:
5738:
5716:
5715:
5711:
5681:
5680:
5676:
5663:
5659:
5646:
5642:
5612:
5611:
5607:
5586:
5585:
5581:
5565:
5564:
5560:
5544:
5543:
5539:
5532:
5517:
5516:
5512:
5495:
5491:
5478:
5477:
5473:
5450:(11): 632–633.
5437:
5436:
5429:
5381:
5380:
5376:
5368:
5364:
5357:
5342:
5341:
5337:
5318:
5317:
5313:
5309:
5304:
5250:
5242:α-reliable path
5202:
5171:
5165:
5162:
5155:needs expansion
5140:
5080:
5079:
5068:
5051:
5040:
5034:
5031:
5016:
5000:
4989:
4977:
4944:
4914:
4860:
4787:
4756:
4734:
4733:
4706:
4683:
4682:
4667: log
4655:
4632:
4631:
4591:
4581:
4570:
4569:
4546:
4545:
4503:
4483:
4468:
4457:
4456:
4434:
4433:
4401:
4390:
4389:
4366:
4365:
4357:Time complexity
4349:
4325:
4303:
4302:
4275:
4272:
4250:
4249:
4207:
4187:
4172:
4161:
4160:
4138:
4137:
4095:
4084:
4083:
4051:
4050:
4031:
4028:
4006:
4005:
3997:Time complexity
3989:
3973:
3965:
3961:
3958:
3882:
3863:
3823:
3822:
3793:
3788:
3787:
3779:Time complexity
3768:
3712:
3711:
3687:
3686:
3678:Time complexity
3664:
3655:
3649:
3646:
3630:
3614:
3571:
3553:
3539:
3538:
3513:
3512:
3465:
3451:
3450:
3425:
3424:
3413:
3361:
3350:
3349:
3323:
3318:
3317:
3295:
3294:
3283:
3240:
3215:
3194:
3174:
3173:
3170:with sketching
3144:
3143:
3132:
3092:
3059:
3054:
3053:
3030:
3025:
3024:
2998:
2997:
2986:
2943:
2918:
2900:
2889:
2888:
2860:
2859:
2804:
2803:
2775:
2774:
2712:
2711:
2680:
2679:
2625:
2624:
2593:
2592:
2545:
2544:
2517:
2516:
2478:
2467:
2466:
2442:
2441:
2433:Time complexity
2422:
2413:
2407:
2404:
2388:
2322:
2321:
2296:
2295:
2238:
2237:
2183:
2169:
2168:
2102:
2101:
2052:
2051:
2014:
2013:
1975:
1954:
1953:
1924:
1923:
1866:
1865:
1834:
1833:
1774:
1773:
1742:
1741:
1697:
1686:
1685:
1657:
1656:
1613:
1602:
1601:
1577:
1576:
1529:
1528:
1501:
1500:
1462:
1451:
1450:
1426:
1425:
1417:Time complexity
1395:
1378:
1371:
1336:Time complexity
1328:
1284:
1283:
1264: log
1250:
1228:
1227:
1194:
1172:
1171:
1151:
1129:
1128:
1119:Time complexity
1110:
1105:
1048:
957:
956:
917:
879:
878:
859:
858:
839:
826:
821:
820:
793:
788:
787:
763:
744:
731:
717:
716:
697:
692:
691:
672:
671:
652:
651:
618:
617:
592:
587:
586:
565:
560:
559:
532:
527:
526:
496:
482:
481:
457:
452:
451:
430:
425:
424:
403:
398:
397:
372:
371:
352:
351:
320:
319:
292:
287:
286:
285:is adjacent to
265:
260:
259:
211:
192:
179:
165:
164:
134:
86:
75:
69:
66:
56:Please help to
55:
39:
35:
28:
23:
22:
15:
12:
11:
5:
7358:
7356:
7348:
7347:
7342:
7337:
7332:
7330:Graph distance
7327:
7325:Network theory
7317:
7316:
7310:
7309:
7304:
7301:
7300:
7298:
7297:
7295:Reverse-delete
7292:
7287:
7282:
7276:
7274:
7268:
7267:
7265:
7264:
7259:
7254:
7249:
7247:Floyd–Warshall
7244:
7239:
7233:
7231:
7225:
7224:
7222:
7221:
7216:
7211:
7206:
7201:
7196:
7195:
7194:
7184:
7179:
7178:
7177:
7172:
7162:
7157:
7152:
7147:
7146:
7145:
7140:
7135:
7123:
7117:
7115:
7109:
7108:
7098:
7096:
7095:
7088:
7081:
7073:
7067:
7066:
7046:
7041:10.1.1.32.9856
7027:
7021:
7004:
7001:
6999:
6998:
6960:Williams, Ryan
6956:
6946:(1/2): 37–40.
6935:
6923:(3): 330–353.
6908:
6888:(3): 362–394.
6873:
6864:
6854:(4): 501–507.
6843:
6837:
6824:
6813:(2): 224–230.
6802:
6775:
6769:
6748:
6736:
6727:
6675:
6649:(1): 295–309.
6624:
6584:
6557:
6551:
6534:
6514:(2): 148–168.
6494:
6467:
6447:(3): 596–615.
6425:
6419:
6387:
6378:
6346:
6336:(2): 187–190.
6325:
6319:
6289:
6271:(2): 129–174.
6252:
6238:
6207:
6169:
6119:(April 1990).
6111:
6109:
6106:
6104:
6103:
6092:(2): 143–154.
6076:
6049:
6021:
6012:
6005:
5987:
5980:
5962:
5955:
5935:
5916:
5889:
5862:(2): 277–311.
5842:
5813:
5788:
5773:
5736:
5725:(1): 378–384.
5709:
5690:(3): 209–232.
5674:
5657:
5640:
5605:
5588:Sanders, Peter
5579:
5558:
5537:
5531:978-0321295354
5530:
5510:
5489:
5471:
5427:
5374:
5362:
5355:
5335:
5310:
5308:
5305:
5303:
5300:
5299:
5298:
5292:
5287:
5282:
5277:
5272:
5267:
5262:
5257:
5249:
5246:
5201:
5198:
5173:
5172:
5152:
5150:
5139:
5136:
5135:
5134:
5131:
5119:
5115:
5111:
5107:
5102:
5098:
5094:
5090:
5087:
5067:
5064:
5053:
5052:
5003:
5001:
4994:
4988:
4985:
4976:
4973:
4957:P = NP problem
4943:
4940:
4913:
4910:
4909:
4908:
4903:
4900:
4897:
4892:
4887:
4884:
4859:
4856:
4848:transportation
4793:websites like
4786:
4783:
4780:
4779:
4774:
4754:
4742:
4730:
4729:
4724:
4704:
4691:
4679:
4678:
4673:
4653:
4640:
4628:
4627:
4625:Quantum search
4622:
4611:
4607:
4603:
4598:
4594:
4588:
4584:
4580:
4577:
4567:
4554:
4542:
4541:
4536:
4525:
4518:
4514:
4510:
4506:
4502:
4499:
4496:
4493:
4490:
4486:
4481:
4475:
4471:
4467:
4464:
4454:
4442:
4430:
4429:
4424:
4413:
4408:
4404:
4400:
4397:
4387:
4374:
4362:
4361:
4358:
4355:
4348:
4347:Directed graph
4345:
4342:
4341:
4335:
4323:
4311:
4299:
4298:
4293:
4273:
4270:
4258:
4246:
4245:
4240:
4229:
4222:
4218:
4214:
4210:
4206:
4203:
4200:
4197:
4194:
4190:
4185:
4179:
4175:
4171:
4168:
4158:
4146:
4134:
4133:
4127:
4116:
4113:
4110:
4107:
4102:
4098:
4094:
4091:
4081:
4070:
4067:
4064:
4061:
4058:
4047:
4046:
4041:
4029:
4026:
4014:
4002:
4001:
3998:
3995:
3988:
3985:
3970:Shimbel (1953)
3957:
3954:
3953:
3952:
3951:
3950:
3942:
3941:
3940:
3932:
3931:
3930:
3927:
3924:
3916:
3915:
3914:
3906:
3905:
3904:
3901:
3900:
3899:
3896:
3881:
3878:
3862:
3859:
3856:
3855:
3850:
3839:
3836:
3833:
3830:
3820:
3818:
3805:
3802:
3797:
3784:
3783:
3780:
3777:
3774:
3767:
3764:
3761:
3760:
3757:
3746:
3742:
3738:
3735:
3730:
3725:
3722:
3719:
3709:
3707:
3695:
3683:
3682:
3679:
3676:
3673:
3663:
3660:
3657:
3656:
3636:
3634:
3622:
3621:
3609:
3598:
3595:
3592:
3587:
3584:
3581:
3578:
3574:
3568:
3564:
3560:
3556:
3552:
3549:
3546:
3536:
3533:
3521:
3509:
3508:
3503:
3492:
3489:
3486:
3483:
3480:
3477:
3472:
3468:
3464:
3461:
3458:
3448:
3445:
3433:
3421:
3420:
3408:
3397:
3394:
3391:
3388:
3383:
3380:
3377:
3374:
3371:
3368:
3364:
3360:
3357:
3347:
3330:
3326:
3315:
3303:
3291:
3290:
3278:
3267:
3264:
3261:
3256:
3253:
3250:
3247:
3243:
3239:
3236:
3231:
3228:
3225:
3222:
3218:
3214:
3209:
3205:
3201:
3197:
3193:
3190:
3187:
3184:
3181:
3171:
3164:
3152:
3140:
3139:
3127:
3116:
3113:
3108:
3105:
3102:
3099:
3095:
3089:
3086:
3083:
3080:
3077:
3074:
3070:
3066:
3062:
3051:
3037:
3033:
3018:
3006:
2994:
2993:
2981:
2970:
2967:
2964:
2959:
2956:
2953:
2950:
2946:
2942:
2939:
2934:
2931:
2928:
2925:
2921:
2915:
2911:
2907:
2903:
2899:
2896:
2886:
2880:
2868:
2856:
2855:
2846:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2801:
2795:
2783:
2771:
2770:
2757:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2709:
2707:Fibonacci heap
2700:
2688:
2676:
2675:
2670:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2632:
2622:
2613:
2601:
2589:
2588:
2575:
2564:
2561:
2558:
2555:
2552:
2542:
2537:
2525:
2513:
2512:
2507:
2496:
2493:
2490:
2485:
2481:
2477:
2474:
2464:
2462:
2450:
2438:
2437:
2434:
2431:
2428:
2421:
2418:
2415:
2414:
2394:
2392:
2380:
2379:
2374:
2363:
2358:
2354:
2351:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2319:
2316:
2304:
2292:
2291:
2286:
2275:
2269:
2265:
2262:
2257:
2254:
2251:
2248:
2245:
2235:
2233:
2230:
2229:
2220:
2209:
2206:
2203:
2198:
2194:
2190:
2186:
2182:
2179:
2176:
2166:
2161:
2158:
2157:
2148:
2137:
2132:
2128:
2125:
2121:
2118:
2115:
2112:
2109:
2099:
2097:
2094:
2093:
2088:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2049:
2034:
2022:
2010:
2009:
2006:
1995:
1991:
1987:
1982:
1978:
1972:
1969:
1964:
1961:
1951:
1944:
1932:
1920:
1919:
1910:
1899:
1895:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1863:
1861:Fibonacci heap
1854:
1842:
1830:
1829:
1824:
1813:
1809:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1771:
1762:
1750:
1738:
1737:
1720:
1709:
1704:
1700:
1696:
1693:
1683:
1677:
1665:
1653:
1652:
1647:
1636:
1632:
1628:
1625:
1620:
1616:
1612:
1609:
1599:
1597:
1585:
1573:
1572:
1559:
1548:
1545:
1542:
1539:
1536:
1526:
1521:
1509:
1497:
1496:
1491:
1480:
1477:
1474:
1469:
1465:
1461:
1458:
1448:
1446:
1434:
1422:
1421:
1418:
1415:
1412:
1394:
1391:
1370:
1367:
1364:
1363:
1361:
1347:
1341:
1340:
1337:
1334:
1327:
1324:
1321:
1320:
1314:
1304:
1292:
1280:
1279:
1276:Fibonacci heap
1269:
1251:
1248:
1236:
1224:
1223:
1213:
1195:
1192:
1180:
1168:
1167:
1162:
1152:
1149:
1137:
1125:
1124:
1121:
1116:
1109:
1106:
1104:
1101:
1093:
1092:
1086:
1076:
1070:
1064:
1058:
1047:
1044:
1040:
1039:
1024:
1013:
982:
979:
976:
973:
970:
967:
964:
944:
941:
936:
933:
930:
927:
924:
920:
916:
913:
908:
905:
902:
897:
894:
891:
887:
866:
845:
842:
838:
833:
829:
808:
805:
800:
796:
775:
770:
766:
762:
759:
756:
751:
747:
743:
738:
734:
730:
727:
724:
703:
700:
679:
659:
638:
634:
631:
628:
625:
599:
595:
572:
568:
545:
542:
539:
535:
514:
509:
506:
503:
499:
495:
492:
489:
464:
460:
437:
433:
410:
406:
385:
382:
379:
359:
350:. Such a path
339:
336:
333:
330:
327:
305:
302:
299:
295:
272:
268:
247:
244:
241:
238:
235:
232:
229:
226:
223:
218:
214:
210:
207:
204:
199:
195:
191:
186:
182:
178:
175:
172:
133:
130:
88:
87:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
7357:
7346:
7343:
7341:
7338:
7336:
7333:
7331:
7328:
7326:
7323:
7322:
7320:
7307:
7302:
7296:
7293:
7291:
7288:
7286:
7283:
7281:
7278:
7277:
7275:
7273:
7269:
7263:
7260:
7258:
7255:
7253:
7250:
7248:
7245:
7243:
7240:
7238:
7235:
7234:
7232:
7230:
7229:Shortest path
7226:
7220:
7217:
7215:
7212:
7210:
7207:
7205:
7204:Fringe search
7202:
7200:
7197:
7193:
7190:
7189:
7188:
7185:
7183:
7180:
7176:
7173:
7171:
7170:Lexicographic
7168:
7167:
7166:
7163:
7161:
7158:
7156:
7153:
7151:
7148:
7144:
7141:
7139:
7136:
7134:
7131:
7130:
7129:
7128:
7124:
7122:
7119:
7118:
7116:
7114:
7110:
7105:
7101:
7094:
7089:
7087:
7082:
7080:
7075:
7074:
7071:
7059:
7052:
7047:
7042:
7037:
7033:
7028:
7024:
7022:9798655831896
7018:
7014:
7013:
7007:
7006:
7002:
6995:
6991:
6987:
6983:
6978:
6973:
6969:
6967:
6961:
6957:
6953:
6949:
6945:
6941:
6936:
6931:
6926:
6922:
6918:
6914:
6909:
6905:
6901:
6896:
6891:
6887:
6883:
6879:
6874:
6870:
6865:
6861:
6857:
6853:
6849:
6844:
6840:
6834:
6830:
6825:
6820:
6816:
6812:
6808:
6803:
6798:
6793:
6789:
6785:
6781:
6776:
6772:
6766:
6762:
6758:
6754:
6749:
6745:
6741:
6737:
6733:
6728:
6724:
6720:
6715:
6710:
6706:
6702:
6701:
6696:
6692:
6688:
6684:
6676:
6672:
6668:
6664:
6660:
6656:
6652:
6648:
6644:
6638:
6634:
6629:
6625:
6621:
6617:
6612:
6607:
6603:
6599:
6598:
6593:
6589:
6585:
6580:
6575:
6571:
6567:
6563:
6558:
6554:
6548:
6544:
6540:
6535:
6531:
6527:
6522:
6517:
6513:
6509:
6508:
6503:
6499:
6495:
6491:
6487:
6483:
6476:
6472:
6468:
6464:
6460:
6455:
6450:
6446:
6442:
6438:
6434:
6430:
6426:
6422:
6420:0-8186-0591-X
6416:
6412:
6408:
6404:
6400:
6396:
6392:
6388:
6384:
6379:
6375:
6371:
6367:
6363:
6359:
6355:
6351:
6347:
6343:
6339:
6335:
6331:
6326:
6322:
6320:0-262-03293-7
6316:
6312:
6311:
6306:
6302:
6298:
6294:
6290:
6286:
6282:
6278:
6274:
6270:
6266:
6262:
6258:
6253:
6249:
6245:
6241:
6235:
6231:
6227:
6222:
6217:
6213:
6208:
6204:
6200:
6195:
6190:
6186:
6182:
6178:
6174:
6170:
6163:
6159:
6155:
6150:
6145:
6141:
6137:
6133:
6129:
6122:
6118:
6113:
6112:
6107:
6099:
6095:
6091:
6087:
6080:
6077:
6072:
6068:
6064:
6060:
6053:
6050:
6045:
6041:
6037:
6033:
6025:
6022:
6016:
6013:
6008:
6002:
5998:
5991:
5988:
5983:
5977:
5973:
5966:
5963:
5958:
5952:
5948:
5947:
5939:
5936:
5931:
5927:
5920:
5917:
5912:
5908:
5904:
5900:
5893:
5890:
5885:
5881:
5877:
5873:
5869:
5865:
5861:
5857:
5853:
5846:
5843:
5835:
5831:
5824:
5817:
5814:
5808:
5803:
5799:
5792:
5789:
5784:
5780:
5776:
5770:
5766:
5762:
5757:
5752:
5748:
5740:
5737:
5732:
5728:
5724:
5720:
5713:
5710:
5705:
5701:
5697:
5693:
5689:
5685:
5678:
5675:
5671:
5667:
5661:
5658:
5654:
5650:
5644:
5641:
5636:
5632:
5628:
5624:
5620:
5616:
5609:
5606:
5601:
5597:
5593:
5589:
5583:
5580:
5574:
5569:
5562:
5559:
5553:
5548:
5541:
5538:
5533:
5527:
5523:
5522:
5514:
5511:
5506:
5500:
5492:
5490:9780262533058
5486:
5482:
5475:
5472:
5467:
5463:
5458:
5453:
5449:
5445:
5441:
5434:
5432:
5428:
5423:
5419:
5415:
5411:
5407:
5403:
5398:
5393:
5389:
5385:
5378:
5375:
5372:, p. 655
5371:
5366:
5363:
5358:
5352:
5348:
5347:
5339:
5336:
5331:
5327:
5323:
5322:
5315:
5312:
5306:
5301:
5296:
5293:
5291:
5288:
5286:
5283:
5281:
5278:
5276:
5273:
5271:
5268:
5266:
5263:
5261:
5258:
5255:
5252:
5251:
5247:
5245:
5243:
5239:
5234:
5232:
5228:
5224:
5220:
5216:
5210:
5206:
5199:
5197:
5195:
5190:
5187:
5185:
5181:
5169:
5160:
5156:
5153:This section
5151:
5148:
5144:
5143:
5137:
5132:
5109:
5096:
5085:
5077:
5073:
5072:
5071:
5065:
5063:
5061:
5049:
5046:
5038:
5035:December 2015
5028:
5024:
5020:
5014:
5013:
5009:
5004:This section
5002:
4998:
4993:
4992:
4986:
4984:
4982:
4974:
4972:
4970:
4966:
4962:
4958:
4954:
4950:
4941:
4939:
4936:
4934:
4930:
4925:
4923:
4919:
4911:
4907:
4904:
4901:
4898:
4896:
4893:
4891:
4888:
4885:
4882:
4878:
4874:
4873:
4872:
4868:
4864:
4858:Road networks
4857:
4855:
4853:
4849:
4845:
4841:
4836:
4834:
4829:
4827:
4823:
4819:
4814:
4812:
4807:
4802:
4800:
4796:
4792:
4784:
4778:
4775:
4771:
4767:
4764: +
4763:
4759:
4755:
4732:
4731:
4728:
4725:
4721:
4717:
4714: +
4713:
4709:
4705:
4681:
4680:
4677:
4674:
4670:
4666:
4663: +
4662:
4658:
4654:
4630:
4629:
4626:
4623:
4605:
4601:
4596:
4592:
4586:
4582:
4575:
4568:
4544:
4543:
4540:
4539:Williams 2014
4537:
4516:
4512:
4508:
4500:
4497:
4494:
4484:
4479:
4473:
4469:
4462:
4455:
4432:
4431:
4428:
4425:
4406:
4402:
4395:
4388:
4364:
4363:
4359:
4356:
4353:
4352:
4346:
4339:
4336:
4332:
4328:
4324:
4301:
4300:
4297:
4294:
4290:
4286:
4282:
4278:
4274:
4248:
4247:
4244:
4243:Williams 2014
4241:
4220:
4216:
4212:
4204:
4201:
4198:
4188:
4183:
4177:
4173:
4166:
4159:
4136:
4135:
4131:
4128:
4111:
4108:
4105:
4100:
4096:
4089:
4082:
4062:
4059:
4049:
4048:
4045:
4042:
4038:
4034:
4030:
4004:
4003:
3999:
3996:
3993:
3992:
3986:
3984:
3980:
3976:
3971:
3955:
3948:
3947:
3946:
3943:
3938:
3937:
3936:
3933:
3928:
3925:
3922:
3921:
3920:
3917:
3912:
3911:
3910:
3907:
3902:
3897:
3894:
3893:
3891:
3890:
3889:
3886:
3885:
3884:
3879:
3877:
3874:
3870:
3867:
3866:Network flows
3860:
3854:
3851:
3834:
3828:
3821:
3819:
3803:
3800:
3786:
3785:
3781:
3778:
3775:
3772:
3771:
3765:
3758:
3740:
3736:
3733:
3728:
3723:
3717:
3710:
3708:
3685:
3684:
3680:
3677:
3674:
3671:
3670:
3667:
3661:
3653:
3650:December 2012
3644:
3640:
3637:This list is
3635:
3628:
3627:
3618:
3613:
3610:
3593:
3590:
3582:
3576:
3572:
3566:
3562:
3558:
3554:
3550:
3544:
3537:
3534:
3511:
3510:
3507:
3504:
3487:
3484:
3481:
3478:
3475:
3470:
3466:
3462:
3456:
3449:
3446:
3423:
3422:
3417:
3412:
3409:
3392:
3389:
3386:
3378:
3372:
3369:
3366:
3362:
3355:
3348:
3345:
3328:
3324:
3316:
3293:
3292:
3287:
3282:
3279:
3262:
3259:
3251:
3245:
3241:
3237:
3234:
3226:
3220:
3216:
3207:
3203:
3199:
3195:
3191:
3188:
3179:
3172:
3169:
3165:
3142:
3141:
3136:
3131:
3128:
3114:
3111:
3103:
3097:
3093:
3084:
3078:
3075:
3072:
3068:
3064:
3060:
3052:
3035:
3031:
3022:
3019:
2996:
2995:
2990:
2985:
2982:
2965:
2962:
2954:
2948:
2944:
2940:
2937:
2929:
2923:
2919:
2913:
2909:
2905:
2901:
2894:
2887:
2884:
2881:
2858:
2857:
2854:
2850:
2847:
2827:
2824:
2821:
2815:
2809:
2802:
2799:
2796:
2773:
2772:
2769:
2765:
2761:
2758:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2717:
2710:
2708:
2704:
2701:
2678:
2677:
2674:
2671:
2654:
2651:
2648:
2645:
2642:
2639:
2636:
2630:
2623:
2621:
2617:
2614:
2591:
2590:
2587:
2583:
2579:
2576:
2559:
2556:
2550:
2543:
2541:
2538:
2515:
2514:
2511:
2508:
2491:
2488:
2483:
2479:
2472:
2465:
2463:
2440:
2439:
2435:
2432:
2429:
2426:
2425:
2419:
2411:
2408:February 2011
2402:
2398:
2395:This list is
2393:
2386:
2385:
2378:
2375:
2356:
2352:
2349:
2345:
2342:
2339:
2336:
2333:
2327:
2320:
2317:
2294:
2293:
2290:
2287:
2267:
2263:
2260:
2255:
2252:
2249:
2243:
2236:
2234:
2232:
2231:
2228:
2224:
2221:
2204:
2201:
2196:
2192:
2188:
2184:
2180:
2174:
2167:
2165:
2162:
2160:
2159:
2156:
2152:
2149:
2130:
2126:
2123:
2119:
2116:
2113:
2107:
2100:
2098:
2096:
2095:
2092:
2089:
2072:
2069:
2066:
2063:
2057:
2050:
2047:
2043:
2039:
2035:
2012:
2011:
2007:
1989:
1985:
1980:
1976:
1970:
1967:
1959:
1952:
1949:
1945:
1922:
1921:
1918:
1914:
1911:
1893:
1889:
1886:
1883:
1880:
1877:
1871:
1864:
1862:
1858:
1855:
1832:
1831:
1828:
1825:
1807:
1803:
1800:
1794:
1791:
1788:
1779:
1772:
1770:
1766:
1763:
1740:
1739:
1736:
1732:
1729:, Minty (see
1728:
1727:Dijkstra 1959
1724:
1721:
1702:
1698:
1691:
1684:
1681:
1678:
1655:
1654:
1651:
1648:
1630:
1626:
1623:
1618:
1614:
1607:
1600:
1598:
1575:
1574:
1571:
1567:
1563:
1560:
1543:
1540:
1534:
1527:
1525:
1522:
1499:
1498:
1495:
1492:
1475:
1472:
1467:
1463:
1456:
1449:
1447:
1424:
1423:
1419:
1416:
1413:
1410:
1409:
1406:
1404:
1400:
1392:
1390:
1386:
1382:
1376:
1368:
1362:
1359:
1356: +
1355:
1351:
1348:
1346:
1343:
1342:
1338:
1335:
1332:
1331:
1325:
1318:
1315:
1312:
1308:
1305:
1282:
1281:
1277:
1273:
1270:
1267:
1263:
1260: +
1259:
1255:
1252:
1226:
1225:
1221:
1217:
1214:
1211:
1207:
1204: +
1203:
1199:
1196:
1170:
1169:
1166:
1165:Dijkstra 1959
1163:
1160:
1156:
1153:
1127:
1126:
1122:
1120:
1117:
1114:
1113:
1107:
1102:
1100:
1098:
1090:
1087:
1084:
1083:sparse graphs
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1052:
1051:
1045:
1043:
1038:in the graph.
1037:
1033:
1029:
1025:
1022:
1018:
1014:
1011:
1007:
1003:
1002:
1001:
999:
994:
977:
968:
965:
962:
942:
934:
931:
928:
925:
922:
918:
911:
906:
903:
900:
895:
892:
889:
885:
864:
843:
840:
836:
831:
827:
806:
803:
798:
794:
768:
764:
760:
757:
754:
749:
745:
741:
736:
732:
725:
722:
701:
698:
677:
657:
629:
626:
623:
615:
597:
593:
570:
566:
543:
540:
537:
533:
507:
504:
501:
497:
490:
487:
478:
462:
458:
435:
431:
408:
404:
383:
380:
377:
357:
337:
334:
331:
328:
325:
303:
300:
297:
293:
270:
266:
245:
242:
239:
236:
233:
230:
227:
224:
216:
212:
208:
205:
202:
197:
193:
189:
184:
180:
173:
170:
162:
158:
153:
151:
147:
143:
139:
131:
129:
125:
123:
119:
115:
111:
107:
103:
94:
84:
81:
73:
63:
59:
53:
52:
46:
41:
32:
31:
19:
7237:Bellman–Ford
7228:
7126:
7031:
7011:
6963:
6943:
6939:
6920:
6916:
6885:
6881:
6868:
6851:
6847:
6828:
6810:
6806:
6790:(1): 47–74.
6787:
6783:
6756:
6743:
6740:Moore, E. F.
6731:
6707:(1): 91–93.
6704:
6698:
6690:
6686:
6682:
6646:
6642:
6636:
6632:
6601:
6595:
6569:
6565:
6542:
6511:
6505:
6481:
6471:Gabow, H. N.
6444:
6440:
6398:
6357:
6353:
6333:
6329:
6309:
6268:
6264:
6211:
6184:
6180:
6149:1721.1/47994
6131:
6127:
6108:Bibliography
6089:
6085:
6079:
6065:(1): 25–37.
6062:
6058:
6052:
6035:
6031:
6024:
6015:
5996:
5990:
5971:
5965:
5945:
5938:
5929:
5925:
5919:
5902:
5892:
5859:
5855:
5845:
5829:
5816:
5797:
5791:
5746:
5739:
5722:
5718:
5712:
5687:
5683:
5677:
5660:
5643:
5618:
5614:
5608:
5595:
5582:
5561:
5540:
5520:
5513:
5480:
5474:
5447:
5443:
5387:
5383:
5377:
5365:
5345:
5338:
5320:
5314:
5265:Flow network
5241:
5237:
5235:
5230:
5226:
5211:
5207:
5203:
5191:
5188:
5176:
5163:
5159:adding to it
5154:
5069:
5056:
5041:
5032:
5017:Please help
5005:
4978:
4945:
4937:
4926:
4915:
4869:
4865:
4861:
4837:
4830:
4815:
4811:Rubik's Cube
4803:
4788:
4785:Applications
4777:Hagerup 2000
4769:
4765:
4761:
4757:
4719:
4715:
4711:
4707:
4668:
4664:
4660:
4656:
4330:
4326:
4288:
4284:
4280:
4276:
4036:
4032:
3978:
3974:
3959:
3944:
3934:
3918:
3908:
3887:
3883:
3872:
3871:
3865:
3864:
3861:Applications
3665:
3647:
3612:Fineman 2023
3050:flow solver
2853:Johnson 1977
2768:Johnson 1977
2673:Johnson 1977
2582:Bellman 1958
2578:Shimbel 1955
2405:
2151:Johnson 1981
2045:
2042:bucket queue
1827:Johnson 1977
1650:Dantzig 1960
1566:Bellman 1958
1562:Shimbel 1955
1402:
1396:
1384:
1380:
1372:
1357:
1353:
1349:
1310:
1306:
1265:
1261:
1257:
1253:
1216:Johnson 1977
1209:
1205:
1201:
1197:
1158:
1154:
1094:
1049:
1041:
1035:
1031:
1027:
1020:
1016:
1009:
1005:
997:
995:
715:is the path
479:
163:of vertices
154:
135:
126:
112:between two
105:
102:graph theory
99:
76:
67:
48:
7155:Beam search
7121:α–β pruning
6759:. pp.
6604:(1): 1–13.
6572:(1): 3–23.
6360:: 269–271.
5800:: 261–270.
5280:Pathfinding
5166:August 2014
4961:NP-complete
4959:). Another
4953:NP-complete
4799:Google Maps
4791:web mapping
4727:Pettie 2004
4338:Thorup 1999
2620:binary heap
2377:Thorup 2004
1769:binary heap
1317:Thorup 1999
1220:binary heap
614:real-valued
62:introducing
7319:Categories
7242:Dijkstra's
6968:(STOC '14)
6267:. Ser. A.
6221:2203.03456
5756:2108.01036
5302:References
4906:Hub labels
4818:networking
4360:Algorithm
4000:Algorithm
3639:incomplete
2586:Moore 1959
2397:incomplete
2227:Gabow 1985
2223:Gabow 1983
1570:Moore 1959
1046:Algorithms
612:. Given a
258:such that
142:undirected
132:Definition
45:references
7285:Kruskal's
7280:Borůvka's
7252:Johnson's
7036:CiteSeerX
6977:1312.6680
6904:207654795
6807:Oper. Res
6635:(log log
6620:207678246
6374:123284777
6248:247958461
6187:: 87–90.
5911:901424694
5876:1436-4646
5802:CiteSeerX
5783:210706773
5573:1410.6220
5499:cite book
5414:0097-5397
5006:does not
4886:Arc flags
4877:A* search
4602:
4498:
4489:Ω
4202:
4193:Ω
4109:
4101:ω
4066:∞
3801:≥
3776:Algorithm
3737:
3675:Algorithm
3591:
3485:
3476:
3390:
3325:ℓ
3260:
3235:
3112:
3032:ℓ
2963:
2938:
2849:Dial 1969
2739:
2652:
2510:Ford 1956
2430:Algorithm
2353:
2346:
2264:
2202:
2127:
2120:
2091:Dial 1969
1986:
1890:
1804:
1682:with list
1627:
1494:Ford 1956
1414:Algorithm
1333:Algorithm
972:→
904:−
886:∑
758:…
633:→
381:−
329:≤
243:×
240:⋯
237:×
231:×
225:∈
206:…
70:June 2009
7175:Parallel
7058:Archived
6689:log log
6671:35703411
6590:(1977).
6500:(1985).
6473:(1983).
6435:(1987).
6397:(1984).
6175:(1958).
6162:Archived
5834:Archived
5635:11761485
5600:Archived
5422:14253494
5248:See also
5180:semiring
4902:Labeling
4854:design.
4844:robotics
4795:MapQuest
2048:buckets)
2040:using a
1946:Quantum
844:′
702:′
161:sequence
146:directed
140:whether
114:vertices
6994:3238994
6761:267–276
6723:0700028
6663:0683047
6641:time".
6530:0828519
6463:7904683
6285:1392160
6203:0102435
6158:5499589
5901:(ed.).
5692:Bibcode
5466:6754003
5027:removed
5012:sources
4354:Weights
3994:Weights
3945:Repeat:
3782:Author
3773:Weights
3681:Author
3672:Weights
3166:Robust
2436:Author
2427:Weights
1420:Author
1411:Weights
1339:Author
1123:Author
1115:Weights
786:(where
450:. (The
122:weights
58:improve
7290:Prim's
7113:Search
7038:
7019:
6992:
6902:
6835:
6767:
6721:
6669:
6661:
6618:
6549:
6528:
6461:
6417:
6372:
6317:
6283:
6246:
6236:
6201:
6156:
6003:
5978:
5953:
5909:
5882:
5874:
5804:
5781:
5771:
5633:
5528:
5487:
5464:
5420:
5412:
5353:
4931:. The
4920:, see
4850:, and
2318:Thorup
525:where
138:graphs
104:, the
47:, but
7262:Yen's
7100:Graph
7061:(PDF)
7054:(PDF)
6972:arXiv
6900:S2CID
6667:S2CID
6616:S2CID
6478:(PDF)
6459:S2CID
6370:S2CID
6244:S2CID
6216:arXiv
6165:(PDF)
6154:S2CID
6124:(PDF)
5928:[
5884:79739
5880:S2CID
5837:(PDF)
5826:(PDF)
5779:S2CID
5751:arXiv
5631:S2CID
5568:arXiv
5547:arXiv
5462:S2CID
5418:S2CID
5392:arXiv
5307:Notes
5295:TRILL
4875:ALT (
4816:In a
3023:with
2705:with
2618:with
2044:with
1859:with
1767:with
396:from
150:mixed
148:, or
118:graph
7219:SSS*
7143:SMA*
7138:LPA*
7133:IDA*
7104:tree
7102:and
7017:ISBN
6833:ISBN
6765:ISBN
6680:"An
6547:ISBN
6415:ISBN
6403:IEEE
6315:ISBN
6234:ISBN
6001:ISBN
5976:ISBN
5951:ISBN
5907:OCLC
5872:ISSN
5769:ISBN
5526:ISBN
5505:link
5485:ISBN
5410:ISSN
5351:ISBN
5229:and
5217:and
5074:The
5010:any
5008:cite
4979:The
4852:VLSI
3617:help
3416:help
3286:help
3135:help
2989:help
1026:The
1015:The
1004:The
819:and
585:and
480:Let
335:<
318:for
157:path
110:path
6982:doi
6948:doi
6925:doi
6890:doi
6856:doi
6815:doi
6792:doi
6788:312
6709:doi
6651:doi
6606:doi
6574:doi
6516:doi
6486:doi
6449:doi
6407:doi
6362:doi
6338:doi
6273:doi
6226:doi
6189:doi
6144:hdl
6136:doi
6094:doi
6067:doi
6040:doi
5864:doi
5761:doi
5727:doi
5700:doi
5688:168
5623:doi
5452:doi
5402:doi
5326:doi
5161:.
5021:by
4820:or
4797:or
4593:log
4587:2.5
4495:log
4199:log
4106:log
3734:log
3645:.
3573:log
3482:log
3467:log
3387:log
3242:log
3217:log
3094:log
2945:log
2920:log
2736:log
2649:log
2403:.
2350:log
2343:log
2261:log
2185:log
2124:log
2117:log
1977:log
1887:log
1801:log
1733:),
1624:log
1036:v'
690:to
423:to
100:In
7321::
7199:D*
7182:B*
7127:A*
6990:MR
6988:.
6980:.
6944:11
6942:.
6921:69
6919:.
6915:.
6898:.
6886:46
6884:.
6880:.
6852:15
6850:.
6809:.
6786:.
6782:.
6763:.
6755:.
6719:MR
6717:.
6703:.
6697:.
6665:.
6659:MR
6657:.
6647:15
6645:.
6614:.
6602:24
6600:.
6594:.
6570:55
6568:.
6564:.
6526:MR
6524:.
6512:31
6510:.
6504:.
6480:.
6457:.
6445:34
6443:.
6439:.
6431:;
6413:.
6393:;
6368:.
6356:.
6332:.
6303:;
6299:;
6295:;
6281:MR
6279:.
6269:73
6263:.
6242:.
6232:.
6224:.
6199:MR
6197:.
6185:16
6183:.
6179:.
6160:.
6152:.
6142:.
6132:37
6130:.
6126:.
6090:21
6088:.
6063:21
6061:.
6036:42
6034:.
5878:.
5870:.
5860:85
5858:.
5854:.
5828:.
5777:.
5767:.
5759:.
5723:40
5721:.
5698:.
5686:.
5629:.
5619:28
5617:.
5598:.
5594:.
5501:}}
5497:{{
5460:.
5448:12
5446:.
5442:.
5430:^
5416:.
5408:.
5400:.
5388:35
5386:.
5324:.
5196:.
5186:.
4924:.
4846:,
4762:EV
4712:EV
4661:EV
4331:EV
4291:))
4281:EV
3983:.
3966:v'
3964:,
2906:10
2762:,
2584:,
2580:,
2225:,
2153:,
1915:,
1725:,
1568:,
1564:,
1383:+
1379:Θ(
1278:)
1222:)
1200:((
1099:.
1034:,
144:,
7092:e
7085:t
7078:v
7044:.
7025:.
6996:.
6984::
6974::
6954:.
6950::
6933:.
6927::
6906:.
6892::
6862:.
6858::
6841:.
6821:.
6817::
6811:8
6800:.
6794::
6773:.
6725:.
6711::
6705:6
6693:)
6691:D
6687:m
6685:(
6683:O
6673:.
6653::
6639:)
6637:D
6633:O
6622:.
6608::
6582:.
6576::
6555:.
6532:.
6518::
6492:.
6488::
6465:.
6451::
6423:.
6409::
6376:.
6364::
6358:1
6344:.
6340::
6334:6
6323:.
6287:.
6275::
6250:.
6228::
6218::
6205:.
6191::
6146::
6138::
6100:.
6096::
6073:.
6069::
6046:.
6042::
6009:.
5984:.
5959:.
5913:.
5886:.
5866::
5810:.
5785:.
5763::
5753::
5733:.
5729::
5706:.
5702::
5694::
5637:.
5625::
5576:.
5570::
5555:.
5549::
5534:.
5507:)
5493:.
5468:.
5454::
5424:.
5404::
5394::
5359:.
5332:.
5328::
5168:)
5164:(
5130:.
5118:)
5114:|
5110:E
5106:|
5101:|
5097:V
5093:|
5089:(
5086:O
5048:)
5042:(
5037:)
5033:(
5029:.
5015:.
4883:)
4772:)
4770:V
4766:V
4760:(
4758:O
4741:N
4722:)
4720:V
4716:V
4710:(
4708:O
4690:R
4671:)
4669:V
4665:V
4659:(
4657:O
4639:R
4610:)
4606:V
4597:2
4583:V
4579:(
4576:O
4553:R
4524:)
4517:2
4513:/
4509:1
4505:)
4501:V
4492:(
4485:2
4480:/
4474:3
4470:V
4466:(
4463:O
4441:N
4412:)
4407:3
4403:V
4399:(
4396:O
4373:R
4333:)
4329:(
4327:O
4310:N
4289:V
4287:,
4285:E
4279:(
4277:O
4271:+
4257:R
4228:)
4221:2
4217:/
4213:1
4209:)
4205:V
4196:(
4189:2
4184:/
4178:3
4174:V
4170:(
4167:O
4145:N
4115:)
4112:V
4097:V
4093:(
4090:O
4069:}
4063:,
4060:1
4057:{
4039:)
4037:V
4035:(
4033:O
4027:+
4013:R
3981:)
3979:V
3977:(
3975:O
3962:v
3838:)
3835:V
3832:(
3829:O
3804:0
3796:R
3745:)
3741:N
3729:V
3724:E
3721:(
3718:O
3694:Z
3652:)
3648:(
3619:)
3597:)
3594:V
3586:)
3583:1
3580:(
3577:O
3567:9
3563:/
3559:8
3555:V
3551:E
3548:(
3545:O
3520:R
3491:)
3488:L
3479:V
3471:8
3463:E
3460:(
3457:O
3432:Z
3418:)
3396:)
3393:L
3382:)
3379:1
3376:(
3373:o
3370:+
3367:1
3363:E
3359:(
3356:O
3329:1
3302:Z
3288:)
3266:)
3263:L
3255:)
3252:1
3249:(
3246:O
3238:V
3230:)
3227:1
3224:(
3221:O
3213:)
3208:2
3204:/
3200:3
3196:V
3192:+
3189:E
3186:(
3183:(
3180:O
3151:Z
3137:)
3115:L
3107:)
3104:1
3101:(
3098:O
3088:)
3085:1
3082:(
3079:o
3076:+
3073:3
3069:/
3065:4
3061:E
3036:p
3005:Z
2991:)
2969:)
2966:L
2958:)
2955:1
2952:(
2949:O
2941:V
2933:)
2930:1
2927:(
2924:O
2914:7
2910:/
2902:E
2898:(
2895:O
2867:Z
2834:)
2831:)
2828:L
2825:+
2822:E
2819:(
2816:V
2813:(
2810:O
2782:Z
2745:)
2742:V
2733:V
2730:+
2727:E
2724:V
2721:(
2718:O
2687:R
2658:)
2655:V
2646:V
2643:+
2640:E
2637:V
2634:(
2631:O
2600:R
2563:)
2560:E
2557:V
2554:(
2551:O
2524:R
2495:)
2492:L
2489:E
2484:2
2480:V
2476:(
2473:O
2449:R
2410:)
2406:(
2362:)
2357:V
2340:V
2337:+
2334:E
2331:(
2328:O
2303:N
2274:)
2268:L
2256:V
2253:+
2250:E
2247:(
2244:O
2208:)
2205:L
2197:V
2193:/
2189:E
2181:E
2178:(
2175:O
2136:)
2131:L
2114:E
2111:(
2108:O
2076:)
2073:V
2070:L
2067:+
2064:E
2061:(
2058:O
2046:L
2021:N
1994:)
1990:V
1981:2
1971:E
1968:V
1963:(
1960:O
1931:R
1898:)
1894:V
1884:V
1881:+
1878:E
1875:(
1872:O
1841:R
1812:)
1808:V
1798:)
1795:V
1792:+
1789:E
1786:(
1783:(
1780:O
1749:R
1708:)
1703:2
1699:V
1695:(
1692:O
1664:R
1635:)
1631:V
1619:2
1615:V
1611:(
1608:O
1584:R
1547:)
1544:E
1541:V
1538:(
1535:O
1508:R
1479:)
1476:L
1473:E
1468:2
1464:V
1460:(
1457:O
1433:R
1403:L
1387:)
1385:V
1381:E
1360:)
1358:V
1354:E
1352:(
1350:O
1313:)
1311:E
1309:(
1307:O
1291:N
1274:(
1268:)
1266:V
1262:V
1258:E
1256:(
1254:O
1249:+
1235:R
1218:(
1212:)
1210:V
1206:V
1202:E
1198:O
1193:+
1179:R
1161:)
1159:V
1157:(
1155:O
1150:+
1136:R
1085:.
1032:v
1021:v
1010:v
981:}
978:1
975:{
969:E
966::
963:f
943:.
940:)
935:1
932:+
929:i
926:,
923:i
919:e
915:(
912:f
907:1
901:n
896:1
893:=
890:i
865:n
841:v
837:=
832:n
828:v
807:v
804:=
799:1
795:v
774:)
769:n
765:v
761:,
755:,
750:2
746:v
742:,
737:1
733:v
729:(
726:=
723:P
699:v
678:v
658:G
637:R
630:E
627::
624:f
598:j
594:v
571:i
567:v
544:j
541:,
538:i
534:e
513:}
508:j
505:,
502:i
498:e
494:{
491:=
488:E
463:i
459:v
436:n
432:v
409:1
405:v
384:1
378:n
358:P
338:n
332:i
326:1
304:1
301:+
298:i
294:v
271:i
267:v
246:V
234:V
228:V
222:)
217:n
213:v
209:,
203:,
198:2
194:v
190:,
185:1
181:v
177:(
174:=
171:P
83:)
77:(
72:)
68:(
54:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
