5912:
5241:
548:
for a slightly simplified transportation map of 64 cities in the
Netherlands (64, so that 6 bits would be sufficient to encode the city number). A year later, he came across another problem from hardware engineers working on the institute's next computer: minimize the amount of wire needed to connect the pins on the back panel of the machine. As a solution, he re-discovered the algorithm known as
5396:
533:
The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.
924:
3425:
A single edge appearing in the optimal solution is removed from the graph, and the optimum solution to this new graph is calculated. Each edge of the original solution is suppressed in turn and a new shortest-path calculated. The secondary solutions are then ranked and presented after the first optimal solution.
782:
considering every node that is closer in terms of shortest path distance until it reaches the destination. When understood in this way, it is clear how the algorithm necessarily finds the shortest path. However, it may also reveal one of the algorithm's weaknesses: its relative slowness in some topologies.
3424:
The functionality of
Dijkstra's original algorithm can be extended with a variety of modifications. For example, sometimes it is desirable to present solutions which are less than mathematically optimal. To obtain a ranked list of less-than-optimal solutions, the optimal solution is first calculated.
1233:
data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes
547:
in 1956 as a programmer to demonstrate the capabilities of a new computer called ARMAC. His objective was to choose both a problem and a solution (that would be produced by computer) that non-computing people could understand. He designed the shortest path algorithm and later implemented it for ARMAC
773:
Continue this process of updating the neighboring intersections with the shortest distances, marking the current intersection as visited, and moving onto a closest unvisited intersection until you have marked the destination as visited. Once you have marked the destination as visited (as is the case
532:
with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later.
781:
This algorithm makes no attempt of direct "exploration" towards the destination as one might expect. Rather, the sole consideration in determining the next "current" intersection is its distance from the starting point. This algorithm therefore expands outward from the starting point, interactively
760:
the unvisited intersection with this value (the sum) if it is less than the unvisited intersection's current value. In effect, the intersection is relabeled if the path to it through the current intersection is shorter than the previously known paths. To facilitate shortest path identification, in
666:
When we are done considering all of the unvisited neighbors of the current node, mark the current node as visited and remove it from the unvisited set. This is so that a visited node is never checked again, which is correct because the distance recorded on the current node is minimal (as ensured in
641:
From the unvisited set, select the current node to be the one with the smallest finite distance; initially, this will be the starting node, which has distance zero. If the unvisited set is empty, or contains only nodes with infinite distance (which are unreachable), then the algorithm terminates by
2815:
In common presentations of
Dijkstra's algorithm, initially all nodes are entered into the priority queue. This is, however, not necessary: the algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check
3818:
At the
Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated
268:
Dijkstra's algorithm finds the shortest path from a given source node to every other node. It can also be used to find the shortest path to a specific destination node, by terminating the algorithm once the shortest path to the destination node is known. For example, if the nodes of the graph
269:
represent cities, and the costs of edges represent the average distances between pairs of cities connected by a direct road, then
Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A common application of shortest path algorithms is network
579:
problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are the visited ones, with color representing the distance: the greener, the closer. Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular
769:
and select an unvisited intersection with minimal distance (from the starting point) â or the lowest labelâas the current intersection. Intersections marked as visited are labeled with the shortest path from the starting point to it and will not be revisited or returned to.
2819:
Moreover, not inserting all nodes in a graph makes it possible to extend the algorithm to find the shortest path from a single source to the closest of a set of target nodes on infinite graphs or those too large to represent in memory. The resulting algorithm is called
2353:
to implement extracting minimum efficiently. To perform decrease-key steps in a binary heap efficiently, it is necessary to use an auxiliary data structure that maps each vertex to its position in the heap, and to keep this structure up to date as the priority queue
645:
For the current node, consider all of its unvisited neighbors and update their distances through the current node; compare the newly calculated distance to the one currently assigned to the neighbor and assign it the smaller one. For example, if the current node
1482:
These alternatives can use entirely array-based priority queues without decrease-key functionality, which have been found to achieve even faster computing times in practice. However, the difference in performance was found to be narrower for denser graphs.
47:
778:. In the algorithm's implementations, this is usually done (after the algorithm has reached the destination node) by following the nodes' parents from the destination node up to the starting node; that's why we also keep track of each node's parent.
1234:
in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these shortest paths between two given nodes we would use a path finding algorithm on the new graph, such as
2816:
whether the key is in the queue; if it is, decrease its key, otherwise insert it). This variant has the same worst-case bounds as the common variant, but maintains a smaller priority queue in practice, speeding up the queue operations.
3414:
3463:
it often is allowed.) It is possible to adapt
Dijkstra's algorithm to handle negative weight edges by combining it with the Bellman-Ford algorithm (to remove negative edges and detect negative cycles); such an algorithm is called
2095:
59:. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.
642:
going to step 6. If we are only concerned about the path to a target node, we may terminate here if the current node is the target node. Otherwise, we can continue to find the shortest paths to all reachable nodes.
2805:
3475:
is a generalization of
Dijkstra's algorithm that cuts down on the size of the subgraph that must be explored, if additional information is available that provides a lower bound on the "distance" to the target.
3455:. The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed. (This statement assumes that a "path" is allowed to repeat vertices. In
662:
is 6 + 2 = 8. If B was previously marked with a distance greater than 8, then update it to 8 (the path to B through A is shorter). Otherwise, keep its current distance (the path to B through A is not the
2287:
729:. This is done not to imply that there is an infinite distance, but to note that those intersections have not been visited yet. Some variants of this method leave the intersections' distances
630:
value: for the starting node, it is zero, and for all other nodes, it is infinity, since initially no path is known to these nodes. During execution of the algorithm, the distance of a node
2959:" followed by shortest-path computation between these transit nodes using a "highway". Combinations of such techniques may be needed for optimal practical performance on specific problems.
3491:
that connects all nodes in the graph; Dijkstra is concerned with only two nodes. Prim's does not evaluate the total weight of the path from the starting node, only the individual edges.
5809:
3189:
2439:
2937:), graph pruning to determine which nodes are likely to form the middle segment of shortest paths (reach-based routing), and hierarchical decompositions of the input graph that reduce
2681:
2584:
761:
pencil, mark the road with an arrow pointing to the relabeled intersection if you label/relabel it, and erase all others pointing to it. After you have updated the distances to each
459:
182:
2500:
3261:
5434:
3113:
2162:
2130:
473:
with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can indeed be improved further, as detailed in
340:
484:
Dijkstra's algorithm is commonly used on graphs where the edge weights are positive integers or real numbers. It can be generalized to any graph where the edge weights are
5219:
3875:
3055:
5680:
1961:
5804:
3516:
point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the
2331:
296:
data structure for selecting the shortest paths known so far. Before more advanced priority queue structures were discovered, Dijkstra's original algorithm ran in
1991:
1915:
1877:
1847:
1611:
373:
3270:
3671:
3651:
3631:
3611:
3591:
3568:
3548:
2985:
1585:
4199:
The third classical minimum spanning tree algorithm was discovered by JarnĂk and rediscovered by Prim and
Dikstra; it is commonly known as Prim's algorithm.
737:
at each iteration. For the first iteration, the current intersection will be the starting point, and the distance to it (the intersection's label) will be
4429:
3723:
1266:
offer optimal implementations for those 3 operations. As the algorithm is slightly different in appearance, it is mentioned here, in pseudocode as well:
5068:
1636:
To prove this claim, we proceed by contradiction. If there were a shorter path, then this shorter path either contains another unvisited node or not.
2006:
569:
5818:
5427:
6298:
1704:
because otherwise w would have been picked by the priority queue instead of v. This is a contradiction, since it has already been established that
4212:
4120:
5163:
5535:
5212:
5673:
5156:
4626:
4597:
4438:
4300:
4091:
4003:
3963:
5134:
4842:
Investigation of Model
Techniques â First Annual Report â 6 June 1956 â 1 July 1957 â A Study of Model Techniques for Communication Systems
2987:), specialized queues which take advantage of this fact can be used to speed up Dijkstra's algorithm. The first algorithm of this type was
2689:
1558:. Its distance is defined to be zero, which is the shortest distance, since negative weights are not allowed. Hence, the hypothesis holds.
6425:
6379:
5841:
5420:
4197:, CBMS_NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, p. 75,
4149:
462:
1413:
Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only
5893:
5754:
5513:
5170:
3936:
3497:
can be viewed as a special-case of
Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a FIFO queue.
5861:
5142:
5085:
4692:
4401:
2334:
230:
572:
Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a target node (upper right, green) in a
544:
31:
5399:
5972:
5666:
5191:
2903:
is the length of the shortest path from the start node to any node satisfying the "goal" predicate, each edge has cost at least
2333:
edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a
5126:
6249:
5911:
5600:
5318:
4854:
4139:
In a route-finding problem, Felner finds that the queue can be a factor 500â600 smaller, taking some 40% of the running time.
1492:
5198:
3745:
818:
array contains pointers to previous-hop nodes on the shortest path from source to the given vertex (equivalently, it is the
2198:
6357:
5977:
5518:
5299:
5061:
3980:
1258:. As mentioned earlier, using such a data structure can lead to faster computing times than using a basic queue. Notably,
725:. Dijkstra's algorithm initially marks the distance (from the starting point) to every other intersection on the map with
6293:
6261:
5590:
4809:
Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks".
3708:
5259:
3460:
2590:
1185:(there might be several different ones of the same length). Then instead of storing only a single node in each entry of
762:
103:
5205:
3504:
can be viewed as a continuous version of Dijkstra's algorithm which computes the geodesic distance on a triangle mesh.
927:
A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting
6420:
6400:
6342:
5967:
5094:
4516:
Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea (2010).
3429:
6288:
6244:
5846:
5580:
5177:
3698:
3444:
1438:
Yet another alternative is to add nodes unconditionally to the priority queue and to instead check after extraction (
5149:
4019:
SzczeĆniak, Ireneusz; Jajszczyk, Andrzej; WoĆșna-SzczeĆniak, BoĆŒena (2019). "Generic Dijkstra for optical networks".
6415:
6405:
6137:
5866:
5102:
4674:
4391:
251:
6027:
6430:
6410:
5689:
5110:
5030:
4708:
6212:
5623:
4840:
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957).
3126:
2364:
5638:
5054:
2604:
2594:
2512:
1963:
for any simple graph, but that simplification disregards the fact that in some problems, other upper bounds on
752:
the distance to every unvisited intersection that is directly connected to it. This is done by determining the
616:
611:. Dijkstra's algorithm will initially start with infinite distances and will try to improve them step by step.
278:
6074:
4342:
670:
Once the loop exits (steps 3â5), every visited node will contain its shortest distance from the starting node.
390:
113:
5118:
4876:
6435:
6155:
5871:
5557:
5376:
5294:
3703:
774:
with any visited intersection), you have determined the shortest path to it from the starting point and can
496:
5749:
5464:
5184:
6347:
6332:
6222:
6100:
5726:
5693:
5628:
5595:
5476:
4811:
4618:
3887:
3713:
3465:
2447:
1496:
286:
86:
4064:
SzczeĆniak, Ireneusz; WoĆșna-SzczeĆniak, BoĆŒena (2023), "Generic Dijkstra: Correctness and tractability",
3202:
6236:
6202:
6105:
6047:
5928:
5734:
5714:
5615:
5572:
5313:
5284:
3488:
2593:
time complexity is lower than the worst-case: assuming edge costs are drawn independently from a common
525:
485:
478:
466:
247:
243:
95:
4243:
3940:
3064:
2135:
2103:
1644:
be the first unvisited node on this shorter path. By the induction hypothesis, the shortest paths from
4572:
4122:
Position Paper: Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Dijkstra's Algorithm
299:
6283:
6110:
6022:
5508:
5503:
5481:
5308:
5279:
5264:
4662:
4379:
4227:
4126:
3718:
3501:
3494:
2956:
2926:
756:
of the distance between an unvisited intersection and the value of the current intersection and then
585:
553:
5658:
5036:
3892:
2897:
The complexity of this algorithm can be expressed in an alternative way for very large graphs: when
6352:
6217:
6170:
6160:
6012:
6000:
5813:
5796:
5701:
5633:
5469:
5040:
4190:
3693:
3513:
3484:
1537:
when traveling via visited nodes only, or infinity if no such path exists. (Note: we do not assume
714:
549:
76:
6087:
6056:
6042:
6032:
5823:
5649:
5530:
5225:
5077:
5008:
4973:
4944:
4909:
4828:
4797:
4727:
4589:
4537:
4483:
4097:
4069:
4046:
4028:
3905:
3871:
3853:
3058:
3002:
1235:
489:
293:
262:
259:
5739:
5605:
1920:
4281:
Gass, Saul; Fu, Michael (2013). "Dijkstra's Algorithm". In Gass, Saul I; Fu, Michael C (eds.).
568:
6095:
5773:
5552:
5493:
5371:
5341:
4688:
4622:
4593:
4434:
4420:
4397:
4296:
4087:
3999:
3959:
504:
488:, provided the subsequent labels (a subsequent label is produced when traversing an edge) are
4157:
3801:
3195:). Finally, the best algorithms in this special case are as follows. The algorithm given by (
2834:
node â start frontier â priority queue containing node only expanded â empty set
2299:
560:). Dijkstra published the algorithm in 1959, two years after Prim and 29 years after JarnĂk.
6175:
6165:
6069:
5946:
5851:
5833:
5786:
5697:
5274:
5249:
4998:
4965:
4934:
4899:
4891:
4863:
4820:
4787:
4755:
4717:
4666:
4658:
4529:
4475:
4375:
4286:
4235:
4079:
4038:
3991:
3951:
3897:
3845:
3681:
3480:
3472:
2188:
270:
195:
72:
68:
4684:
4358:
Priority Queues and Dijkstra's Algorithm â UTCS Technical Report TR-07-54 â 12 October 2007
3409:{\displaystyle O(|E|+|V|\min\{(\log |V|)^{1/3+\varepsilon },(\log C)^{1/4+\varepsilon }\})}
6191:
5456:
5443:
5304:
5269:
4767:
4739:
4172:
3678:
866:
returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes
576:
342:
106:
2358:
changes. With a self-balancing binary search tree or binary heap, the algorithm requires
1966:
1890:
1852:
1822:
1590:
348:
17:
4231:
6179:
6064:
5951:
5885:
5856:
5447:
5356:
5351:
5289:
4670:
4518:"Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm"
4460:
4387:
4356:
4239:
3656:
3636:
3616:
3596:
3576:
3553:
3533:
3448:
2970:
2503:
2350:
2346:
2184:
1880:
1570:
1259:
757:
557:
470:
384:
91:
5412:
4987:"Undirected single-source shortest paths with positive integer weights in linear time"
4556:
4517:
2824:(UCS) in the artificial intelligence literature and can be expressed in pseudocode as
1883:. The complexity bound depends mainly on the data structure used to represent the set
1281:): 2 create vertex priority queue Q 3 4 dist â 0
538:
Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001
6394:
6337:
6321:
5547:
5381:
5366:
5012:
4875:
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April 1990).
4867:
4771:
4743:
4101:
3932:
3909:
5240:
4948:
4832:
4364:. Austin, Texas: The University of Texas at Austin, Department of Computer Sciences.
4083:
4050:
3857:
6275:
5781:
5361:
5336:
4977:
4913:
4849:
4801:
4731:
4541:
4487:
4424:
3456:
3447:
can be used on graphs with negative edge weights, as long as the graph contains no
2996:
2930:
2342:
2293:
1263:
1189:
we would store all nodes satisfying the relaxation condition. For example, if both
634:
is the length of the shortest path discovered so far between the starting node and
255:
2444:
time in the worst case; for connected graphs this time bound can be simplified to
2191:. In this case, extract-minimum is simply a linear search through all vertices in
741:. For subsequent iterations (after the first), the current intersection will be a
46:
2925:
Further optimizations of Dijkstra's algorithm for the single-target case include
6362:
5744:
5498:
4986:
4271:, PrĂĄce MoravskĂ© PĆĂrodovÄdeckĂ© SpoleÄnosti, 6, 1930, pp. 57â63. (in Czech)
2338:
1617:
be the next visited node according to the algorithm, i.e. the node with minimum
1246:
A min-priority queue is an abstract data type that provides 3 basic operations:
2090:{\displaystyle \Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),}
1449:) that it isn't revisiting, or that no shorter connection was found yet in the
5346:
4969:
4383:
4291:
3955:
3120:
1753:
already, because of the inductive hypothesis, and these values are unchanged.
791:
282:
4759:
4355:
Chen, M.; Chowdhury, R. A.; Ramachandran, V.; Roche, D. L.; Tong, L. (2007).
650:
is marked with a distance of 6, and the edge connecting it with its neighbor
4776:"Fibonacci heaps and their uses in improved network optimization algorithms"
4680:
4533:
4479:
3849:
1780:, we would have found it previously, and if there were a shorter path using
581:
529:
521:
517:
239:
4704:"Algorithm 360: Shortest-path forest with topological ordering [H]"
4343:
https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key
4042:
2891:
is in frontier with higher cost replace existing node with
1453:
block. This can be done by additionally extracting the associated priority
975:: 4 dist â INFINITY 5 prev â UNDEFINED 6 add
5003:
4939:
4922:
4748:
Fibonacci heaps and their uses in improved network optimization algorithms
4722:
4703:
3523:
In fact, Dijkstra's explanation of the logic behind the algorithm, namely
1213:(because the edge cost is the same in both cases), then we would add both
923:
528:, which I designed in about twenty minutes. One morning I was shopping in
5764:
4824:
3995:
3633:, knowledge of the latter implies the knowledge of the minimal path from
1811:
Bounds of the running time of Dijkstra's algorithm on a graph with edges
573:
4904:
4895:
4792:
4775:
2911:, then the algorithm's worst-case time and space complexity are both in
1776:
using visited nodes only. If there were a shorter path that did not use
6084:
3901:
1173:
A more general problem would be to find all the shortest paths between
931:
and prev. Blue lines indicate where relaxing happens, i.e., connecting
902:. If this path is shorter than the current shortest path recorded for
2800:{\displaystyle O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).}
543:
Dijkstra thought about the shortest path problem when working at the
4066:
NOMS 2023-2023 IEEE/IFIP Network Operations and Management Symposium
1158:
is the list of vertices constituting one of the shortest paths from
375:
is the number of nodes. The idea of this algorithm is also given in
4573:
Online version of the paper with interactive computational modules.
4557:"Dijkstra's algorithm revisited: the dynamic programming connexion"
4074:
4033:
3836:
Frana, Phil (August 2010). "An Interview with Edsger W. Dijkstra".
3746:"Dijkstra's algorithm revisited: the dynamic programming connexion"
2179:
The simplest version of Dijkstra's algorithm stores the vertex set
5046:
3479:
The process that underlies Dijkstra's algorithm is similar to the
3437:
922:
567:
274:
1688:. As the edge costs are positive, the minimal cost of going from
5562:
5486:
5230:
4751:
3433:
500:
477:. Additionally, if preprocessing is allowed, algorithms such as
6319:
6135:
5998:
5926:
5712:
5662:
5416:
5050:
4174:
Reflections on "A note on two problems in connexion with graphs
4125:. Proc. 4th Int'l Symp. on Combinatorial Search. Archived from
3119:). Another interesting variant based on a combination of a new
1819:
can be expressed as a function of the number of edges, denoted
1328:
11 Q.add_with_priority(v, INFINITY) 12 13 14
3530:
Find the path of minimum total length between two given nodes
2995:) for graphs with positive integer edge weights, which uses a
1052:
If we are only interested in a shortest path between vertices
5026:
4396:(4th ed.). MIT Press and McGraw-Hill. pp. 622â623.
3428:
Dijkstra's algorithm is usually the working principle behind
5910:
4923:"Recent results on the single-source shortest paths problem"
4750:. 25th Annual Symposium on Foundations of Computer Science.
2967:
When arc weights are small integers (bounded by a parameter
5542:
5525:
1887:. In the following, upper bounds can be simplified because
1541:
is the actual shortest distance for unvisited nodes, while
219:
204:
4283:
Encyclopedia of Operations Research and Management Science
3774:
1721:
be the last but one node on the shortest path. That means
682:
For ease of understanding, this discussion uses the terms
503:
and formulated as an instance of the more general idea of
387:
priority queue to optimize the running time complexity to
1207:
and both of them lie on different shortest paths through
798:
is an array that contains the current distances from the
5319:
Philosophy of computer programming and computing science
5213:
Self-stabilizing Systems in Spite of Distributed Control
3192:
3116:
376:
5157:
Solution of a Problem in Concurrent Programming Control
4213:"Shortest connection networks and some generalizations"
51:
Dijkstra's algorithm to find the shortest path between
5135:
Selected Writings on Computing: A Personal Perspective
1554:
The base case is when there is just one visited node,
808:
is the current distance from the source to the vertex
499:, Dijkstra's algorithm or a variant of it is known as
3659:
3639:
3619:
3599:
3579:
3556:
3536:
3273:
3205:
3129:
3067:
3005:
2973:
2907:, and the number of neighbors per node is bounded by
2692:
2607:
2515:
2450:
2367:
2302:
2282:{\displaystyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}
2201:
2138:
2106:
2009:
1969:
1923:
1893:
1855:
1825:
1760:, it will still be true that for each unvisited node
1593:
1573:
393:
351:
302:
281:(Open Shortest Path First). It is also employed as a
231:
222:
210:
207:
116:
4852:(1977). "A Generalization of Dijkstra's Algorithm".
3831:
3829:
3827:
3759:
2934:
1791:
After all nodes are visited, the shortest path from
216:
213:
201:
6274:
6235:
6201:
6190:
6148:
6083:
6055:
6041:
6011:
5960:
5939:
5884:
5832:
5795:
5772:
5763:
5725:
5614:
5571:
5455:
5327:
5248:
5084:
1800:
1765:
1746:
1734:
1730:
1722:
1709:
1705:
1701:
1697:
1677:
1661:
1657:
1622:
1618:
1542:
1538:
1526:
1510:
1435:operation if the node is not already in the queue.
776:
trace your way back following the arrows in reverse
745:to the starting point (this will be easy to find).
198:
102:
82:
64:
5220:On the Cruelty of Really Teaching Computer Science
5164:The Structure of the 'THE'-Multiprogramming System
4780:Journal of the Association for Computing Machinery
4503:Speed-up techniques for shortest-path computations
3665:
3645:
3625:
3605:
3585:
3562:
3542:
3408:
3255:
3183:
3107:
3049:
2979:
2859:solution(node) expanded.add(node)
2799:
2675:
2578:
2494:
2433:
2325:
2281:
2156:
2124:
2089:
1985:
1955:
1909:
1871:
1841:
1749:is already known to be the shortest distance from
1605:
1579:
453:
367:
334:
176:
4956:Thorup, Mikkel (2000). "On RAM priority Queues".
4877:"Faster Algorithms for the Shortest Path Problem"
3948:Algorithms and Data Structures: The Basic Toolbox
3876:"A note on two problems in connexion with graphs"
694:â however, in formal terminology these terms are
277:(Intermediate System to Intermediate System) and
5037:Implementation of Dijkstra's algorithm using TDD
4844:. Cleveland, Ohio: Case Institute of Technology.
4433:(3rd ed.). Prentice Hall. pp. 75, 81.
4021:Journal of Optical Communications and Networking
3309:
1664:respectively. This means the cost of going from
943:, which gives a shorter path from the source to
5143:A Note on Two Problems in Connexion with Graphs
4615:Dynamic Programming: Foundations and Principles
3525:
3123:and the well-known Fibonacci heap runs in time
3061:as the priority queue brings the complexity to
1324:10 dist â INFINITY
1320:9 prev â UNDEFINED
1118:// Do something only if the vertex is reachable
1064:, we can terminate the search after line 10 if
514:
481:can be up to seven orders of magnitude faster.
5027:Oral history interview with Edsger W. Dijkstra
4673:(2001). "Section 24.3: Dijkstra's algorithm".
2848:failure node â frontier.pop()
1725:. That is a contradiction because by the time
884:on line 14 is the length of the path from the
5674:
5428:
5062:
4315:
3981:"On the history of the shortest path problem"
3788:
3684:in the context of the shortest path problem.
2929:variants, goal-directed variants such as the
1129:// Construct the shortest path with a stack S
524:, in general: from given city to given city.
380:
8:
4586:Dynamic Programming: Models and Applications
3784:
3782:
3400:
3312:
1587:visited nodes. We wish to show it holds for
998:with minimum dist 11 remove u from
39:
4501:Wagner, Dorothea; Willhalm, Thomas (2007).
2811:Practical optimizations and infinite graphs
2183:as a linked list or array, and edges as an
1799:consists only of visited nodes. Therefore,
1459:from the queue and only processing further
1170:, or the empty sequence if no path exists.
667:step 3), and thus final. Go back to step 3.
6316:
6232:
6198:
6145:
6132:
6052:
6008:
5995:
5936:
5923:
5769:
5722:
5709:
5681:
5667:
5659:
5435:
5421:
5413:
5192:Programming Considered as a Human Activity
5069:
5055:
5047:
4430:Artificial Intelligence: A Modern Approach
3927:
3925:
3923:
3921:
3919:
3724:Parallel all-pairs shortest path algorithm
3184:{\displaystyle O(|E|+|V|{\sqrt {\log C}})}
2434:{\displaystyle \Theta ((|E|+|V|)\log |V|)}
1996:For any data structure for the vertex set
588:of picking the shortest known path so far.
45:
5002:
4938:
4903:
4791:
4721:
4290:
4114:
4112:
4110:
4073:
4032:
3990:. Documenta Mathematica Series: 155â167.
3891:
3658:
3638:
3618:
3598:
3578:
3555:
3535:
3384:
3380:
3345:
3341:
3332:
3324:
3304:
3296:
3288:
3280:
3272:
3245:
3237:
3220:
3212:
3204:
3165:
3160:
3152:
3144:
3136:
3128:
3082:
3074:
3066:
3036:
3028:
3020:
3012:
3004:
2972:
2784:
2776:
2762:
2754:
2747:
2739:
2736:
2725:
2717:
2709:
2701:
2691:
2676:{\displaystyle \Theta (|V|\log(|E|/|V|))}
2662:
2654:
2649:
2644:
2636:
2622:
2614:
2606:
2579:{\displaystyle \Theta (|E|+|V|\log |V|).}
2565:
2557:
2546:
2538:
2530:
2522:
2514:
2484:
2476:
2465:
2457:
2449:
2423:
2415:
2401:
2393:
2385:
2377:
2366:
2317:
2312:
2303:
2301:
2270:
2265:
2256:
2238:
2233:
2224:
2216:
2208:
2200:
2144:
2143:
2137:
2112:
2111:
2105:
2071:
2070:
2058:
2050:
2037:
2036:
2024:
2016:
2008:
1978:
1970:
1968:
1944:
1939:
1930:
1922:
1902:
1894:
1892:
1864:
1856:
1854:
1834:
1826:
1824:
1784:we would have updated it when processing
1592:
1572:
1074:. Now we can read the shortest path from
526:It is the algorithm for the shortest path
474:
443:
435:
424:
416:
408:
400:
392:
360:
352:
350:
323:
318:
309:
301:
265:in 1956 and published three years later.
166:
158:
147:
139:
131:
123:
115:
5915:Optimization computes maxima and minima.
5127:Predicate Calculus and Program Semantics
4641:
4154:Unsung Heroes in Dutch Computing History
516:What is the shortest way to travel from
454:{\displaystyle \Theta (|E|+|V|\log |V|)}
177:{\displaystyle \Theta (|E|+|V|\log |V|)}
4415:
4413:
4334:cannot ever hold because of the update
3770:
3768:
3735:
2876:is not in expanded and not in frontier
1495:of Dijkstra's algorithm, we proceed by
5395:
5199:How Do We Tell Truths That Might Hurt?
5033:, University of Minnesota, Minneapolis
4195:Data Structures and Network Algorithms
3196:
2935:§ Related problems and algorithms
2296:, that is, graphs with far fewer than
1849:, and the number of vertices, denoted
1656:through visited nodes only have costs
1386:< dist: 19 prev â
1037:< dist: 16 dist â
619:of all the unvisited nodes called the
615:Mark all nodes as unvisited. Create a
550:Prim's minimal spanning tree algorithm
38:
6111:Principal pivoting algorithm of Lemke
3808:. Association for Computing Machinery
3264:
7:
2992:
2495:{\displaystyle \Theta (|E|\log |V|)}
1326:// Unknown distance from source to v
254:, which may represent, for example,
27:Algorithm for finding shortest paths
3593:is a node on the minimal path from
3256:{\displaystyle O(|E|\log \log |V|)}
1768:will be the shortest distance from
765:, mark the current intersection as
709:Suppose you would like to find the
654:has length 2, then the distance to
5755:Successive parabolic interpolation
5171:Go To Statement Considered Harmful
4564:Journal of Control and Cybernetics
4240:10.1002/j.1538-7305.1957.tb01515.x
3459:that is normally not allowed. In
2608:
2516:
2451:
2368:
2250:
2202:
2148:
2145:
2116:
2113:
2075:
2072:
2041:
2038:
2010:
1365:// Go through all v neighbors of u
1335:is not empty:
1295:// associated priority equals dist
1127:is defined:
394:
303:
117:
25:
6075:Projective algorithm of Karmarkar
5206:On the Role of Scientific Thought
3451:reachable from the source vertex
3443:Unlike Dijkstra's algorithm, the
3263:time and the algorithm given by (
3108:{\displaystyle O(|E|\log \log C)}
2683:, giving a total running time of
2335:self-balancing binary search tree
2157:{\displaystyle T_{\mathrm {em} }}
2125:{\displaystyle T_{\mathrm {dk} }}
1680:+ the minimal cost of going from
1545:is the actual shortest distance)
1347:.extract_min()
1148:// Traverse from target to source
1146:â prev
1140:// Push the vertex onto the stack
6070:Ellipsoid algorithm of Khachiyan
5973:Sequential quadratic programming
5810:BroydenâFletcherâGoldfarbâShanno
5394:
5239:
5150:Cooperating Sequential Processes
5095:A Primer of ALGOL 60 Programming
1567:Assume the hypothesis holds for
1499:on the number of visited nodes.
1349:// Remove and return best vertex
1229:. When the algorithm completes,
983:7 dist â 0 8 9
545:Mathematical Center in Amsterdam
465:the fastest known single-source
335:{\displaystyle \Theta (|V|^{2})}
194:
5650:List of graph search algorithms
5178:Notes on Structured Programming
4084:10.1109/NOMS56928.2023.10154322
3508:Dynamic programming perspective
3487:. Prim's purpose is to find a
3420:Related problems and algorithms
1729:is visited, it should have set
1696:is a positive number. However,
748:From the current intersection,
584:as Dijkstra's algorithm uses a
6028:Reduced gradient (FrankâWolfe)
4855:Information Processing Letters
3403:
3377:
3364:
3338:
3333:
3325:
3315:
3305:
3297:
3289:
3281:
3277:
3250:
3246:
3238:
3221:
3213:
3209:
3178:
3161:
3153:
3145:
3137:
3133:
3102:
3083:
3075:
3071:
3044:
3037:
3029:
3021:
3013:
3009:
2785:
2777:
2763:
2755:
2748:
2740:
2726:
2718:
2710:
2702:
2670:
2667:
2663:
2655:
2645:
2637:
2633:
2623:
2615:
2611:
2570:
2566:
2558:
2547:
2539:
2531:
2523:
2519:
2489:
2485:
2477:
2466:
2458:
2454:
2428:
2424:
2416:
2406:
2402:
2394:
2386:
2378:
2374:
2371:
2313:
2304:
2276:
2266:
2257:
2253:
2244:
2234:
2225:
2217:
2209:
2205:
2081:
2059:
2051:
2025:
2017:
2013:
1979:
1971:
1950:
1940:
1931:
1927:
1903:
1895:
1865:
1857:
1835:
1827:
1625:is the shortest distance from
1529:is the shortest distance from
1521:, and for each unvisited node
1513:is the shortest distance from
743:closest unvisited intersection
448:
444:
436:
425:
417:
409:
401:
397:
361:
353:
329:
319:
310:
306:
171:
167:
159:
148:
140:
132:
124:
120:
32:Dykstra's projection algorithm
1:
6358:Spiral optimization algorithm
5978:Successive linear programming
5300:Programming language research
5260:Theoretical computing science
4341:when updating the queue. See
4220:Bell System Technical Journal
3979:Schrijver, Alexander (2012).
2589:When using binary heaps, the
495:In many fields, particularly
6096:Simplex algorithm of Dantzig
5968:Augmented Lagrangian methods
4868:10.1016/0020-0190(77)90002-3
4522:J. Experimental Algorithmics
4269:O jistĂ©m problĂ©mu minimĂĄlnĂm
3941:"Chapter 10. Shortest Paths"
3461:theoretical computer science
3440:being the most common ones.
3430:link-state routing protocols
2164:are the complexities of the
1741:For all other visited nodes
1723:dist + Graph.Edges < dist
285:in other algorithms such as
5111:A Discipline of Programming
3050:{\displaystyle O(|E|+|V|C)}
2830:uniform_cost_search(start)
1390:20 dist â
1041:17 prev â
556:, and also rediscovered by
6452:
6426:Combinatorial optimization
4676:Introduction to Algorithms
4393:Introduction to Algorithms
4305:– via Springer Link.
1956:{\displaystyle O(|V|^{2})}
1803:is the shortest distance.
990:is not empty: 10
890:node to the neighbor node
838:, searches for the vertex
678:
29:
6375:
6328:
6315:
6299:Pushârelabel maximum flow
6144:
6131:
6101:Revised simplex algorithm
6007:
5994:
5935:
5922:
5908:
5721:
5708:
5647:
5390:
5237:
5031:Charles Babbage Institute
4970:10.1137/S0097539795288246
4958:SIAM Journal on Computing
4768:Fredman, Michael Lawrence
4740:Fredman, Michael Lawrence
4709:Communications of the ACM
4461:"Expert computer systems"
4316:Fredman & Tarjan 1984
4292:10.1007/978-1-4419-1153-7
4285:. Vol. 1. Springer.
3956:10.1007/978-3-540-77978-0
3838:Communications of the ACM
3789:Fredman & Tarjan 1987
3744:Moshe Sniedovich (2006).
3573:We use the fact that, if
2999:to obtain a running time
2601:operations is bounded by
2597:, the expected number of
2195:, so the running time is
2000:, the running time is in
1708:+ a positive number <
1676:has the cost of at least
896:if it were to go through
603:be the distance from the
381:Fredman & Tarjan 1984
44:
18:Dijkstra's Algorithm
5824:Symmetric rank-one (SR1)
5805:BerndtâHallâHallâHausman
4760:10.1109/SFCS.1984.715934
4702:Dial, Robert B. (1969).
4505:. STACS. pp. 23â36.
3709:FloydâWarshall algorithm
2595:probability distribution
1717:In the latter case, let
1640:In the former case, let
1505:: For each visited node
1002:12 13
804:to other vertices, i.e.
763:neighboring intersection
40:Dijkstra's algorithm
30:Not to be confused with
6348:Parallel metaheuristics
6156:Approximation algorithm
5867:Powell's dog leg method
5819:DavidonâFletcherâPowell
5715:Unconstrained nonlinear
5558:Monte Carlo tree search
5377:Adriaan van Wijngaarden
5295:Programming methodology
5119:A Method of Programming
4985:Thorup, Mikkel (1999).
4613:Sniedovich, M. (2010).
4555:Sniedovich, M. (2006).
4534:10.1145/1671970.1671976
4480:10.1109/mc.1983.1654302
4455:least-cost-first search
3850:10.1145/1787234.1787249
3750:Control and Cybernetics
3704:Euclidean shortest path
3682:Principle of Optimality
2326:{\displaystyle |V|^{2}}
908:, then the distance of
626:Assign to every node a
497:artificial intelligence
479:contraction hierarchies
467:shortest-path algorithm
258:. It was conceived by
6333:Evolutionary algorithm
5916:
5103:Structured Programming
4921:Raman, Rajeev (1997).
4812:Transportation Science
4584:Denardo, E.V. (2003).
4156:. 2007. Archived from
4119:Felner, Ariel (2011).
4043:10.1364/JOCN.11.000568
3802:"Edsger Wybe Dijkstra"
3699:BellmanâFord algorithm
3675:
3667:
3647:
3627:
3607:
3587:
3564:
3544:
3445:BellmanâFord algorithm
3410:
3257:
3185:
3109:
3051:
2981:
2947:routing to connecting
2801:
2677:
2580:
2496:
2435:
2327:
2283:
2158:
2126:
2091:
1987:
1957:
1911:
1873:
1843:
1607:
1581:
1497:mathematical induction
1242:Using a priority queue
1086:by reverse iteration:
948:
830:the source). The code
589:
541:
455:
369:
336:
178:
6106:Criss-cross algorithm
5929:Constrained nonlinear
5914:
5735:Golden-section search
5616:Minimum spanning tree
5314:Software architecture
5285:Distributed computing
5185:The Humble Programmer
5043:, The Clean Code Blog
5004:10.1145/316542.316548
4940:10.1145/261342.261352
4723:10.1145/363269.363610
4663:Leiserson, Charles E.
4459:Nau, Dana S. (1983).
4380:Leiserson, Charles E.
4171:Dijkstra, Edsger W.,
3988:Documenta Mathematica
3880:Numerische Mathematik
3677:is a paraphrasing of
3668:
3648:
3628:
3608:
3588:
3565:
3545:
3489:minimum spanning tree
3411:
3258:
3186:
3110:
3052:
2982:
2955:to their respective "
2852:node is a goal state
2802:
2678:
2581:
2497:
2436:
2328:
2284:
2159:
2127:
2092:
1988:
1958:
1912:
1874:
1844:
1608:
1582:
1371:â dist + Graph.Edges(
1022:â dist + Graph.Edges(
926:
571:
456:
370:
337:
292:The algorithm uses a
179:
6023:Cutting-plane method
5601:Shortest path faster
5509:Breadth-first search
5504:Bidirectional search
5450:traversal algorithms
5280:Concurrent computing
5265:Software engineering
4825:10.1287/trsc.32.1.65
4754:. pp. 338â346.
4687:. pp. 595â601.
4619:Francis & Taylor
4191:Tarjan, Robert Endre
4160:on 13 November 2013.
3800:Richards, Hamilton.
3719:Longest path problem
3657:
3637:
3617:
3597:
3577:
3554:
3534:
3502:fast marching method
3495:Breadth-first search
3271:
3203:
3127:
3065:
3003:
2971:
2963:Specialized variants
2863:of node's neighbors
2690:
2605:
2513:
2448:
2365:
2300:
2199:
2136:
2104:
2007:
1967:
1921:
1891:
1853:
1823:
1591:
1571:
1503:Invariant hypothesis
1487:Proof of correctness
1394:21
1135:at the beginning of
1093:â empty sequence 2
735:current intersection
475:Specialized variants
391:
377:Leyzorek et al. 1957
349:
300:
190:Dijkstra's algorithm
114:
6353:Simulated annealing
6171:Integer programming
6161:Dynamic programming
6001:Convex optimization
5862:LevenbergâMarquardt
5536:Iterative deepening
5041:Robert Cecil Martin
4896:10.1145/77600.77615
4793:10.1145/28869.28874
4679:(Second ed.).
4232:1957BSTJ...36.1389P
4211:Prim, R.C. (1957).
4129:on 18 February 2020
3742:Controversial, see
3714:Johnson's algorithm
3694:A* search algorithm
3514:dynamic programming
3466:Johnson's algorithm
2822:uniform-cost search
1986:{\displaystyle |E|}
1910:{\displaystyle |E|}
1872:{\displaystyle |V|}
1842:{\displaystyle |E|}
1606:{\displaystyle k+1}
1433:add_with_priority()
1429:decrease_priority()
1417:; then, inside the
1398:.decrease_priority(
1322:// Predecessor of v
1289:.add_with_priority(
1252:decrease_priority()
1248:add_with_priority()
963:): 2 3
850:that has the least
628:distance from start
501:uniform cost search
368:{\displaystyle |V|}
287:Johnson's algorithm
77:Dynamic programming
41:
6421:Routing algorithms
6401:Edsger W. Dijkstra
6033:Subgradient method
5917:
5842:Conjugate gradient
5750:NelderâMead method
5531:Depth-first search
5372:Carel S. Scholten
4991:Journal of the ACM
4884:Journal of the ACM
4590:Dover Publications
4474:(2). IEEE: 63â85.
3902:10.1007/BF01386390
3775:Cormen et al. 2001
3663:
3643:
3623:
3603:
3583:
3560:
3540:
3406:
3253:
3181:
3105:
3059:Van Emde Boas tree
3047:
2977:
2841:frontier is empty
2797:
2673:
2576:
2492:
2431:
2323:
2279:
2154:
2122:
2087:
1983:
1953:
1907:
1869:
1839:
1735:dist + Graph.Edges
1603:
1577:
1379:) 18
1236:depth-first search
1131:5 insert
1030:) 15
1018:: 14
949:
844:in the vertex set
590:
552:(known earlier to
451:
365:
332:
294:min-priority queue
263:Edsger W. Dijkstra
260:computer scientist
174:
90:Usually used with
6416:Search algorithms
6406:1959 in computing
6388:
6387:
6371:
6370:
6311:
6310:
6307:
6306:
6270:
6269:
6231:
6230:
6127:
6126:
6123:
6122:
6119:
6118:
5990:
5989:
5986:
5985:
5906:
5905:
5902:
5901:
5880:
5879:
5656:
5655:
5553:Jump point search
5494:Best-first search
5410:
5409:
5342:Per Brinch Hansen
4772:Tarjan, Robert E.
4744:Tarjan, Robert E.
4667:Rivest, Ronald L.
4659:Cormen, Thomas H.
4628:978-0-8247-4099-3
4599:978-0-486-42810-9
4440:978-0-13-604259-4
4384:Rivest, Ronald L.
4376:Cormen, Thomas H.
4302:978-1-4419-1137-7
4093:978-1-6654-7716-1
4005:978-3-936609-58-5
3965:978-3-540-77977-3
3806:A.M. Turing Award
3666:{\displaystyle R}
3646:{\displaystyle P}
3626:{\displaystyle Q}
3606:{\displaystyle P}
3586:{\displaystyle R}
3563:{\displaystyle Q}
3543:{\displaystyle P}
3193:Ahuja et al. 1990
3176:
3117:Ahuja et al. 1990
2980:{\displaystyle C}
2768:
2506:improves this to
1756:After processing
1580:{\displaystyle k}
1283:// Initialization
826:the given vertex
790:In the following
733:. Now select the
717:on a city map: a
598:distance of node
505:best-first search
486:partially ordered
383:proposed using a
271:routing protocols
187:
186:
16:(Redirected from
6443:
6431:Dutch inventions
6411:Graph algorithms
6317:
6233:
6199:
6176:Branch and bound
6166:Greedy algorithm
6146:
6133:
6053:
6009:
5996:
5937:
5924:
5872:Truncated Newton
5787:Wolfe conditions
5770:
5723:
5710:
5683:
5676:
5669:
5660:
5437:
5430:
5423:
5414:
5398:
5397:
5275:Algorithm design
5243:
5071:
5064:
5057:
5048:
5016:
5006:
4981:
4952:
4942:
4917:
4907:
4881:
4871:
4845:
4836:
4805:
4795:
4763:
4735:
4725:
4698:
4645:
4639:
4633:
4632:
4610:
4604:
4603:
4581:
4575:
4571:
4561:
4552:
4546:
4545:
4513:
4507:
4506:
4498:
4492:
4491:
4465:
4451:
4445:
4444:
4417:
4408:
4407:
4372:
4366:
4365:
4363:
4352:
4346:
4340:
4333:
4325:
4319:
4313:
4307:
4306:
4294:
4278:
4272:
4265:
4259:
4258:
4256:
4254:
4248:
4242:. Archived from
4226:(6): 1389â1401.
4217:
4208:
4202:
4201:
4187:
4181:
4180:
4179:
4168:
4162:
4161:
4146:
4140:
4138:
4136:
4134:
4116:
4105:
4104:
4077:
4068:, pp. 1â7,
4061:
4055:
4054:
4036:
4016:
4010:
4009:
3996:10.4171/dms/6/19
3985:
3976:
3970:
3969:
3945:
3929:
3914:
3913:
3895:
3868:
3862:
3861:
3833:
3822:
3821:
3815:
3813:
3797:
3791:
3786:
3777:
3772:
3763:
3757:
3740:
3672:
3670:
3669:
3664:
3652:
3650:
3649:
3644:
3632:
3630:
3629:
3624:
3612:
3610:
3609:
3604:
3592:
3590:
3589:
3584:
3569:
3567:
3566:
3561:
3549:
3547:
3546:
3541:
3485:Prim's algorithm
3483:process used in
3415:
3413:
3412:
3407:
3399:
3398:
3388:
3360:
3359:
3349:
3336:
3328:
3308:
3300:
3292:
3284:
3262:
3260:
3259:
3254:
3249:
3241:
3224:
3216:
3190:
3188:
3187:
3182:
3177:
3166:
3164:
3156:
3148:
3140:
3114:
3112:
3111:
3106:
3086:
3078:
3056:
3054:
3053:
3048:
3040:
3032:
3024:
3016:
2989:Dial's algorithm
2986:
2984:
2983:
2978:
2954:
2950:
2946:
2921:
2910:
2906:
2902:
2806:
2804:
2803:
2798:
2793:
2789:
2788:
2780:
2769:
2767:
2766:
2758:
2752:
2751:
2743:
2737:
2729:
2721:
2713:
2705:
2682:
2680:
2679:
2674:
2666:
2658:
2653:
2648:
2640:
2626:
2618:
2585:
2583:
2582:
2577:
2569:
2561:
2550:
2542:
2534:
2526:
2501:
2499:
2498:
2493:
2488:
2480:
2469:
2461:
2440:
2438:
2437:
2432:
2427:
2419:
2405:
2397:
2389:
2381:
2357:
2332:
2330:
2329:
2324:
2322:
2321:
2316:
2307:
2288:
2286:
2285:
2280:
2275:
2274:
2269:
2260:
2243:
2242:
2237:
2228:
2220:
2212:
2194:
2182:
2176:, respectively.
2175:
2163:
2161:
2160:
2155:
2153:
2152:
2151:
2131:
2129:
2128:
2123:
2121:
2120:
2119:
2096:
2094:
2093:
2088:
2080:
2079:
2078:
2062:
2054:
2046:
2045:
2044:
2028:
2020:
1999:
1992:
1990:
1989:
1984:
1982:
1974:
1962:
1960:
1959:
1954:
1949:
1948:
1943:
1934:
1916:
1914:
1913:
1908:
1906:
1898:
1886:
1878:
1876:
1875:
1870:
1868:
1860:
1848:
1846:
1845:
1840:
1838:
1830:
1818:
1814:
1802:
1798:
1794:
1787:
1783:
1779:
1775:
1771:
1767:
1763:
1759:
1752:
1748:
1744:
1736:
1732:
1728:
1724:
1720:
1711:
1707:
1703:
1699:
1695:
1691:
1687:
1683:
1679:
1675:
1671:
1667:
1663:
1659:
1655:
1651:
1647:
1643:
1632:
1628:
1624:
1621:. We claim that
1620:
1616:
1612:
1610:
1609:
1604:
1586:
1584:
1583:
1578:
1557:
1544:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1478:
1468:
1458:
1452:
1451:if alt < dist
1448:
1434:
1430:
1426:
1367:17
1337:// The main loop
1293:, 0)
1257:
1253:
1249:
1232:
1228:
1224:
1218:
1212:
1206:
1200:
1194:
1188:
1184:
1178:
1169:
1163:
1157:
1105:prev is defined
1085:
1079:
1073:
1063:
1057:
919:
913:
907:
901:
895:
889:
883:
877:
871:
865:
853:
849:
843:
837:
817:
813:
807:
803:
797:
592:Let us choose a
539:
492:non-decreasing.
460:
458:
457:
452:
447:
439:
428:
420:
412:
404:
374:
372:
371:
366:
364:
356:
341:
339:
338:
333:
328:
327:
322:
313:
242:for finding the
234:
229:
228:
225:
224:
221:
218:
215:
212:
209:
206:
203:
200:
183:
181:
180:
175:
170:
162:
151:
143:
135:
127:
98:for optimization
73:Greedy algorithm
69:Search algorithm
49:
42:
21:
6451:
6450:
6446:
6445:
6444:
6442:
6441:
6440:
6391:
6390:
6389:
6384:
6367:
6324:
6303:
6266:
6227:
6204:
6193:
6186:
6140:
6115:
6079:
6046:
6037:
6014:
6003:
5982:
5956:
5952:Penalty methods
5947:Barrier methods
5931:
5918:
5898:
5894:Newton's method
5876:
5828:
5791:
5759:
5740:Powell's method
5717:
5704:
5687:
5657:
5652:
5643:
5610:
5567:
5451:
5441:
5411:
5406:
5386:
5329:
5323:
5270:Systems science
5251:
5244:
5235:
5231:EWD manuscripts
5226:Selected papers
5080:
5078:Edsger Dijkstra
5075:
5023:
4984:
4955:
4920:
4879:
4874:
4848:
4839:
4808:
4766:
4738:
4716:(11): 632â633.
4701:
4695:
4671:Stein, Clifford
4657:
4654:
4649:
4648:
4640:
4636:
4629:
4612:
4611:
4607:
4600:
4588:. Mineola, NY:
4583:
4582:
4578:
4559:
4554:
4553:
4549:
4515:
4514:
4510:
4500:
4499:
4495:
4463:
4458:
4453:Sometimes also
4452:
4448:
4441:
4421:Russell, Stuart
4419:
4418:
4411:
4404:
4390:(2022) . "22".
4388:Stein, Clifford
4374:
4373:
4369:
4361:
4354:
4353:
4349:
4345:for discussion.
4335:
4328:
4326:
4322:
4314:
4310:
4303:
4280:
4279:
4275:
4266:
4262:
4252:
4250:
4249:on 18 July 2017
4246:
4215:
4210:
4209:
4205:
4189:
4188:
4184:
4177:
4170:
4169:
4165:
4148:
4147:
4143:
4132:
4130:
4118:
4117:
4108:
4094:
4063:
4062:
4058:
4027:(11): 568â577.
4018:
4017:
4013:
4006:
3983:
3978:
3977:
3973:
3966:
3943:
3931:
3930:
3917:
3893:10.1.1.165.7577
3872:Dijkstra, E. W.
3870:
3869:
3865:
3835:
3834:
3825:
3811:
3809:
3799:
3798:
3794:
3787:
3780:
3773:
3766:
3743:
3741:
3737:
3732:
3690:
3655:
3654:
3635:
3634:
3615:
3614:
3595:
3594:
3575:
3574:
3552:
3551:
3532:
3531:
3510:
3422:
3376:
3337:
3269:
3268:
3201:
3200:
3125:
3124:
3063:
3062:
3057:. The use of a
3001:
3000:
2969:
2968:
2965:
2952:
2948:
2938:
2912:
2908:
2904:
2898:
2895:
2813:
2753:
2738:
2700:
2696:
2688:
2687:
2603:
2602:
2511:
2510:
2446:
2445:
2363:
2362:
2355:
2311:
2298:
2297:
2264:
2232:
2197:
2196:
2192:
2180:
2173:
2170:extract-minimum
2139:
2134:
2133:
2107:
2102:
2101:
2066:
2032:
2005:
2004:
1997:
1965:
1964:
1938:
1919:
1918:
1889:
1888:
1884:
1851:
1850:
1821:
1820:
1816:
1812:
1809:
1796:
1792:
1785:
1781:
1777:
1773:
1769:
1761:
1757:
1750:
1742:
1726:
1718:
1693:
1689:
1685:
1681:
1673:
1669:
1665:
1653:
1649:
1645:
1641:
1630:
1626:
1614:
1589:
1588:
1569:
1568:
1555:
1534:
1530:
1522:
1518:
1514:
1506:
1489:
1470:
1460:
1454:
1450:
1439:
1432:
1428:
1418:
1411:
1255:
1251:
1247:
1244:
1230:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1186:
1183:
1180:
1177:
1174:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1084:
1081:
1078:
1075:
1072:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
878:. The variable
876:
873:
870:
867:
863:
859:
855:
851:
848:
845:
842:
839:
831:
815:
812:
809:
805:
802:
799:
795:
788:
707:
706:, respectively.
677:
577:motion planning
566:
540:
537:
513:
471:directed graphs
389:
388:
347:
346:
317:
298:
297:
273:, most notably
232:
197:
193:
112:
111:
89:
75:
71:
60:
35:
28:
23:
22:
15:
12:
11:
5:
6449:
6447:
6439:
6438:
6436:Graph distance
6433:
6428:
6423:
6418:
6413:
6408:
6403:
6393:
6392:
6386:
6385:
6383:
6382:
6376:
6373:
6372:
6369:
6368:
6366:
6365:
6360:
6355:
6350:
6345:
6340:
6335:
6329:
6326:
6325:
6322:Metaheuristics
6320:
6313:
6312:
6309:
6308:
6305:
6304:
6302:
6301:
6296:
6294:FordâFulkerson
6291:
6286:
6280:
6278:
6272:
6271:
6268:
6267:
6265:
6264:
6262:FloydâWarshall
6259:
6254:
6253:
6252:
6241:
6239:
6229:
6228:
6226:
6225:
6220:
6215:
6209:
6207:
6196:
6188:
6187:
6185:
6184:
6183:
6182:
6168:
6163:
6158:
6152:
6150:
6142:
6141:
6136:
6129:
6128:
6125:
6124:
6121:
6120:
6117:
6116:
6114:
6113:
6108:
6103:
6098:
6092:
6090:
6081:
6080:
6078:
6077:
6072:
6067:
6065:Affine scaling
6061:
6059:
6057:Interior point
6050:
6039:
6038:
6036:
6035:
6030:
6025:
6019:
6017:
6005:
6004:
5999:
5992:
5991:
5988:
5987:
5984:
5983:
5981:
5980:
5975:
5970:
5964:
5962:
5961:Differentiable
5958:
5957:
5955:
5954:
5949:
5943:
5941:
5933:
5932:
5927:
5920:
5919:
5909:
5907:
5904:
5903:
5900:
5899:
5897:
5896:
5890:
5888:
5882:
5881:
5878:
5877:
5875:
5874:
5869:
5864:
5859:
5854:
5849:
5844:
5838:
5836:
5830:
5829:
5827:
5826:
5821:
5816:
5807:
5801:
5799:
5793:
5792:
5790:
5789:
5784:
5778:
5776:
5767:
5761:
5760:
5758:
5757:
5752:
5747:
5742:
5737:
5731:
5729:
5719:
5718:
5713:
5706:
5705:
5688:
5686:
5685:
5678:
5671:
5663:
5654:
5653:
5648:
5645:
5644:
5642:
5641:
5639:Reverse-delete
5636:
5631:
5626:
5620:
5618:
5612:
5611:
5609:
5608:
5603:
5598:
5593:
5591:FloydâWarshall
5588:
5583:
5577:
5575:
5569:
5568:
5566:
5565:
5560:
5555:
5550:
5545:
5540:
5539:
5538:
5528:
5523:
5522:
5521:
5516:
5506:
5501:
5496:
5491:
5490:
5489:
5484:
5479:
5467:
5461:
5459:
5453:
5452:
5442:
5440:
5439:
5432:
5425:
5417:
5408:
5407:
5405:
5404:
5391:
5388:
5387:
5385:
5384:
5379:
5374:
5369:
5367:Jaap Zonneveld
5364:
5359:
5357:Leslie Lamport
5354:
5352:Ole-Johan Dahl
5349:
5344:
5339:
5333:
5331:
5325:
5324:
5322:
5321:
5316:
5311:
5305:Program design
5302:
5297:
5292:
5290:Formal methods
5287:
5282:
5277:
5272:
5267:
5262:
5256:
5254:
5246:
5245:
5238:
5236:
5234:
5233:
5228:
5223:
5216:
5209:
5202:
5195:
5188:
5181:
5174:
5167:
5160:
5153:
5146:
5139:
5131:
5123:
5115:
5107:
5099:
5090:
5088:
5082:
5081:
5076:
5074:
5073:
5066:
5059:
5051:
5045:
5044:
5034:
5022:
5021:External links
5019:
5018:
5017:
4997:(3): 362â394.
4982:
4953:
4918:
4890:(2): 213â223.
4872:
4846:
4837:
4806:
4786:(3): 596â615.
4764:
4736:
4699:
4693:
4653:
4650:
4647:
4646:
4634:
4627:
4605:
4598:
4576:
4547:
4508:
4493:
4446:
4439:
4409:
4402:
4367:
4347:
4320:
4308:
4301:
4273:
4260:
4203:
4182:
4163:
4141:
4106:
4092:
4056:
4011:
4004:
3971:
3964:
3937:Sanders, Peter
3933:Mehlhorn, Kurt
3915:
3863:
3823:
3792:
3778:
3764:
3734:
3733:
3731:
3728:
3727:
3726:
3721:
3716:
3711:
3706:
3701:
3696:
3689:
3686:
3662:
3642:
3622:
3602:
3582:
3559:
3539:
3509:
3506:
3449:negative cycle
3421:
3418:
3405:
3402:
3397:
3394:
3391:
3387:
3383:
3379:
3375:
3372:
3369:
3366:
3363:
3358:
3355:
3352:
3348:
3344:
3340:
3335:
3331:
3327:
3323:
3320:
3317:
3314:
3311:
3307:
3303:
3299:
3295:
3291:
3287:
3283:
3279:
3276:
3252:
3248:
3244:
3240:
3236:
3233:
3230:
3227:
3223:
3219:
3215:
3211:
3208:
3180:
3175:
3172:
3169:
3163:
3159:
3155:
3151:
3147:
3143:
3139:
3135:
3132:
3104:
3101:
3098:
3095:
3092:
3089:
3085:
3081:
3077:
3073:
3070:
3046:
3043:
3039:
3035:
3031:
3027:
3023:
3019:
3015:
3011:
3008:
2976:
2964:
2961:
2884:)
2826:
2812:
2809:
2808:
2807:
2796:
2792:
2787:
2783:
2779:
2775:
2772:
2765:
2761:
2757:
2750:
2746:
2742:
2735:
2732:
2728:
2724:
2720:
2716:
2712:
2708:
2704:
2699:
2695:
2672:
2669:
2665:
2661:
2657:
2652:
2647:
2643:
2639:
2635:
2632:
2629:
2625:
2621:
2617:
2613:
2610:
2587:
2586:
2575:
2572:
2568:
2564:
2560:
2556:
2553:
2549:
2545:
2541:
2537:
2533:
2529:
2525:
2521:
2518:
2504:Fibonacci heap
2491:
2487:
2483:
2479:
2475:
2472:
2468:
2464:
2460:
2456:
2453:
2442:
2441:
2430:
2426:
2422:
2418:
2414:
2411:
2408:
2404:
2400:
2396:
2392:
2388:
2384:
2380:
2376:
2373:
2370:
2351:priority queue
2347:Fibonacci heap
2320:
2315:
2310:
2306:
2278:
2273:
2268:
2263:
2259:
2255:
2252:
2249:
2246:
2241:
2236:
2231:
2227:
2223:
2219:
2215:
2211:
2207:
2204:
2185:adjacency list
2172:operations in
2150:
2147:
2142:
2118:
2115:
2110:
2098:
2097:
2086:
2083:
2077:
2074:
2069:
2065:
2061:
2057:
2053:
2049:
2043:
2040:
2035:
2031:
2027:
2023:
2019:
2015:
2012:
1981:
1977:
1973:
1952:
1947:
1942:
1937:
1933:
1929:
1926:
1905:
1901:
1897:
1881:big-O notation
1867:
1863:
1859:
1837:
1833:
1829:
1808:
1805:
1739:
1738:
1714:
1713:
1602:
1599:
1596:
1576:
1562:Inductive step
1488:
1485:
1447:.extract_min()
1363::
1309:: 8
1307:Graph.Vertices
1268:
1260:Fibonacci heap
1243:
1240:
1221:
1215:
1209:
1203:
1197:
1191:
1181:
1175:
1166:
1160:
1154:
1088:
1082:
1076:
1070:
1066:
1060:
1054:
973:Graph.Vertices
950:
916:
914:is updated to
910:
904:
898:
892:
886:
880:
874:
868:
861:
857:
846:
840:
832:u â vertex in
810:
800:
787:
784:
719:starting point
676:
673:
672:
671:
668:
664:
643:
639:
624:
596:, and let the
565:
562:
535:
512:
509:
469:for arbitrary
463:asymptotically
450:
446:
442:
438:
434:
431:
427:
423:
419:
415:
411:
407:
403:
399:
396:
385:Fibonacci heap
363:
359:
355:
331:
326:
321:
316:
312:
308:
305:
250:in a weighted
244:shortest paths
185:
184:
173:
169:
165:
161:
157:
154:
150:
146:
142:
138:
134:
130:
126:
122:
119:
109:
100:
99:
92:priority queue
84:
83:Data structure
80:
79:
66:
62:
61:
50:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6448:
6437:
6434:
6432:
6429:
6427:
6424:
6422:
6419:
6417:
6414:
6412:
6409:
6407:
6404:
6402:
6399:
6398:
6396:
6381:
6378:
6377:
6374:
6364:
6361:
6359:
6356:
6354:
6351:
6349:
6346:
6344:
6341:
6339:
6338:Hill climbing
6336:
6334:
6331:
6330:
6327:
6323:
6318:
6314:
6300:
6297:
6295:
6292:
6290:
6287:
6285:
6282:
6281:
6279:
6277:
6276:Network flows
6273:
6263:
6260:
6258:
6255:
6251:
6248:
6247:
6246:
6243:
6242:
6240:
6238:
6237:Shortest path
6234:
6224:
6221:
6219:
6216:
6214:
6211:
6210:
6208:
6206:
6205:spanning tree
6200:
6197:
6195:
6189:
6181:
6177:
6174:
6173:
6172:
6169:
6167:
6164:
6162:
6159:
6157:
6154:
6153:
6151:
6147:
6143:
6139:
6138:Combinatorial
6134:
6130:
6112:
6109:
6107:
6104:
6102:
6099:
6097:
6094:
6093:
6091:
6089:
6086:
6082:
6076:
6073:
6071:
6068:
6066:
6063:
6062:
6060:
6058:
6054:
6051:
6049:
6044:
6040:
6034:
6031:
6029:
6026:
6024:
6021:
6020:
6018:
6016:
6010:
6006:
6002:
5997:
5993:
5979:
5976:
5974:
5971:
5969:
5966:
5965:
5963:
5959:
5953:
5950:
5948:
5945:
5944:
5942:
5938:
5934:
5930:
5925:
5921:
5913:
5895:
5892:
5891:
5889:
5887:
5883:
5873:
5870:
5868:
5865:
5863:
5860:
5858:
5855:
5853:
5850:
5848:
5845:
5843:
5840:
5839:
5837:
5835:
5834:Other methods
5831:
5825:
5822:
5820:
5817:
5815:
5811:
5808:
5806:
5803:
5802:
5800:
5798:
5794:
5788:
5785:
5783:
5780:
5779:
5777:
5775:
5771:
5768:
5766:
5762:
5756:
5753:
5751:
5748:
5746:
5743:
5741:
5738:
5736:
5733:
5732:
5730:
5728:
5724:
5720:
5716:
5711:
5707:
5703:
5699:
5695:
5691:
5684:
5679:
5677:
5672:
5670:
5665:
5664:
5661:
5651:
5646:
5640:
5637:
5635:
5632:
5630:
5627:
5625:
5622:
5621:
5619:
5617:
5613:
5607:
5604:
5602:
5599:
5597:
5594:
5592:
5589:
5587:
5584:
5582:
5579:
5578:
5576:
5574:
5573:Shortest path
5570:
5564:
5561:
5559:
5556:
5554:
5551:
5549:
5548:Fringe search
5546:
5544:
5541:
5537:
5534:
5533:
5532:
5529:
5527:
5524:
5520:
5517:
5515:
5514:Lexicographic
5512:
5511:
5510:
5507:
5505:
5502:
5500:
5497:
5495:
5492:
5488:
5485:
5483:
5480:
5478:
5475:
5474:
5473:
5472:
5468:
5466:
5463:
5462:
5460:
5458:
5454:
5449:
5445:
5438:
5433:
5431:
5426:
5424:
5419:
5418:
5415:
5403:
5402:
5393:
5392:
5389:
5383:
5382:Niklaus Wirth
5380:
5378:
5375:
5373:
5370:
5368:
5365:
5363:
5360:
5358:
5355:
5353:
5350:
5348:
5345:
5343:
5340:
5338:
5335:
5334:
5332:
5326:
5320:
5317:
5315:
5312:
5310:
5306:
5303:
5301:
5298:
5296:
5293:
5291:
5288:
5286:
5283:
5281:
5278:
5276:
5273:
5271:
5268:
5266:
5263:
5261:
5258:
5257:
5255:
5253:
5250:Main research
5247:
5242:
5232:
5229:
5227:
5224:
5222:
5221:
5217:
5215:
5214:
5210:
5208:
5207:
5203:
5201:
5200:
5196:
5194:
5193:
5189:
5187:
5186:
5182:
5180:
5179:
5175:
5173:
5172:
5168:
5166:
5165:
5161:
5159:
5158:
5154:
5152:
5151:
5147:
5145:
5144:
5140:
5137:
5136:
5132:
5129:
5128:
5124:
5121:
5120:
5116:
5113:
5112:
5108:
5105:
5104:
5100:
5097:
5096:
5092:
5091:
5089:
5087:
5083:
5079:
5072:
5067:
5065:
5060:
5058:
5053:
5052:
5049:
5042:
5038:
5035:
5032:
5028:
5025:
5024:
5020:
5014:
5010:
5005:
5000:
4996:
4992:
4988:
4983:
4979:
4975:
4971:
4967:
4964:(1): 86â109.
4963:
4959:
4954:
4950:
4946:
4941:
4936:
4932:
4928:
4924:
4919:
4915:
4911:
4906:
4901:
4897:
4893:
4889:
4885:
4878:
4873:
4869:
4865:
4861:
4857:
4856:
4851:
4847:
4843:
4838:
4834:
4830:
4826:
4822:
4818:
4814:
4813:
4807:
4803:
4799:
4794:
4789:
4785:
4781:
4777:
4773:
4769:
4765:
4761:
4757:
4753:
4749:
4745:
4741:
4737:
4733:
4729:
4724:
4719:
4715:
4711:
4710:
4705:
4700:
4696:
4694:0-262-03293-7
4690:
4686:
4682:
4678:
4677:
4672:
4668:
4664:
4660:
4656:
4655:
4651:
4644:, p. 270
4643:
4642:Dijkstra 1959
4638:
4635:
4630:
4624:
4620:
4616:
4609:
4606:
4601:
4595:
4591:
4587:
4580:
4577:
4574:
4570:(3): 599â620.
4569:
4565:
4558:
4551:
4548:
4543:
4539:
4535:
4531:
4527:
4523:
4519:
4512:
4509:
4504:
4497:
4494:
4489:
4485:
4481:
4477:
4473:
4469:
4462:
4456:
4450:
4447:
4442:
4436:
4432:
4431:
4426:
4425:Norvig, Peter
4422:
4416:
4414:
4410:
4405:
4403:0-262-04630-X
4399:
4395:
4394:
4389:
4385:
4381:
4377:
4371:
4368:
4360:
4359:
4351:
4348:
4344:
4339:
4331:
4327:Observe that
4324:
4321:
4317:
4312:
4309:
4304:
4298:
4293:
4288:
4284:
4277:
4274:
4270:
4264:
4261:
4245:
4241:
4237:
4233:
4229:
4225:
4221:
4214:
4207:
4204:
4200:
4196:
4192:
4186:
4183:
4176:
4175:
4167:
4164:
4159:
4155:
4151:
4145:
4142:
4128:
4124:
4123:
4115:
4113:
4111:
4107:
4103:
4099:
4095:
4089:
4085:
4081:
4076:
4071:
4067:
4060:
4057:
4052:
4048:
4044:
4040:
4035:
4030:
4026:
4022:
4015:
4012:
4007:
4001:
3997:
3993:
3989:
3982:
3975:
3972:
3967:
3961:
3957:
3953:
3949:
3942:
3938:
3934:
3928:
3926:
3924:
3922:
3920:
3916:
3911:
3907:
3903:
3899:
3894:
3889:
3885:
3881:
3877:
3873:
3867:
3864:
3859:
3855:
3851:
3847:
3843:
3839:
3832:
3830:
3828:
3824:
3820:
3807:
3803:
3796:
3793:
3790:
3785:
3783:
3779:
3776:
3771:
3769:
3765:
3761:
3755:
3751:
3747:
3739:
3736:
3729:
3725:
3722:
3720:
3717:
3715:
3712:
3710:
3707:
3705:
3702:
3700:
3697:
3695:
3692:
3691:
3687:
3685:
3683:
3680:
3674:
3660:
3640:
3620:
3600:
3580:
3571:
3557:
3537:
3529:
3524:
3521:
3519:
3515:
3507:
3505:
3503:
3498:
3496:
3492:
3490:
3486:
3482:
3477:
3474:
3469:
3467:
3462:
3458:
3454:
3450:
3446:
3441:
3439:
3435:
3431:
3426:
3419:
3417:
3395:
3392:
3389:
3385:
3381:
3373:
3370:
3367:
3361:
3356:
3353:
3350:
3346:
3342:
3329:
3321:
3318:
3301:
3293:
3285:
3274:
3266:
3242:
3234:
3231:
3228:
3225:
3217:
3206:
3198:
3194:
3173:
3170:
3167:
3157:
3149:
3141:
3130:
3122:
3118:
3099:
3096:
3093:
3090:
3087:
3079:
3068:
3060:
3041:
3033:
3025:
3017:
3006:
2998:
2994:
2990:
2974:
2962:
2960:
2958:
2957:transit nodes
2945:
2941:
2936:
2932:
2928:
2927:bidirectional
2923:
2919:
2915:
2901:
2894:
2890:
2887:
2883:
2880:frontier.add(
2879:
2875:
2872:
2869:
2866:
2862:
2858:
2855:
2851:
2847:
2844:
2840:
2837:
2833:
2829:
2825:
2823:
2817:
2810:
2794:
2790:
2781:
2773:
2770:
2759:
2744:
2733:
2730:
2722:
2714:
2706:
2697:
2693:
2686:
2685:
2684:
2659:
2650:
2641:
2630:
2627:
2619:
2600:
2596:
2592:
2573:
2562:
2554:
2551:
2543:
2535:
2527:
2509:
2508:
2507:
2505:
2481:
2473:
2470:
2462:
2420:
2412:
2409:
2398:
2390:
2382:
2361:
2360:
2359:
2352:
2348:
2344:
2340:
2336:
2318:
2308:
2295:
2294:sparse graphs
2290:
2271:
2261:
2247:
2239:
2229:
2221:
2213:
2190:
2186:
2177:
2171:
2167:
2140:
2108:
2084:
2067:
2063:
2055:
2047:
2033:
2029:
2021:
2003:
2002:
2001:
1994:
1975:
1945:
1935:
1924:
1899:
1882:
1861:
1831:
1815:and vertices
1806:
1804:
1789:
1754:
1716:
1715:
1639:
1638:
1637:
1634:
1600:
1597:
1594:
1574:
1565:
1563:
1559:
1552:
1550:
1546:
1504:
1500:
1498:
1494:
1491:To prove the
1486:
1484:
1480:
1476:
1473:
1466:
1463:
1457:
1446:
1442:
1436:
1424:
1421:
1416:
1409:
1406:) 22 23
1405:
1401:
1397:
1393:
1389:
1385:
1382:
1378:
1374:
1370:
1366:
1362:
1358:
1354:
1350:
1346:
1342:
1338:
1334:
1331:
1327:
1323:
1319:
1315:
1312:
1308:
1304:
1300:
1296:
1292:
1288:
1284:
1280:
1276:
1272:
1267:
1265:
1261:
1256:extract_min()
1241:
1239:
1237:
1171:
1152:Now sequence
1149:
1145:
1141:
1138:
1134:
1130:
1126:
1123:
1119:
1115:
1111:
1108:
1104:
1100:
1096:
1092:
1087:
1048:
1044:
1040:
1036:
1033:
1029:
1025:
1021:
1017:
1013:
1009:
1005:
1001:
997:
993:
989:
986:
982:
978:
974:
970:
966:
962:
958:
954:
946:
942:
938:
934:
930:
925:
921:
836:with min dist
835:
829:
825:
821:
793:
785:
783:
779:
777:
771:
768:
764:
759:
755:
751:
746:
744:
740:
736:
732:
728:
724:
720:
716:
715:intersections
712:
711:shortest path
705:
701:
697:
693:
689:
685:
681:
674:
669:
665:
661:
657:
653:
649:
644:
640:
637:
633:
629:
625:
622:
621:unvisited set
618:
614:
613:
612:
610:
606:
605:starting node
602:
601:
595:
594:starting node
587:
583:
578:
575:
570:
563:
561:
559:
555:
551:
546:
534:
531:
527:
523:
519:
510:
508:
506:
502:
498:
493:
491:
490:monotonically
487:
482:
480:
476:
472:
468:
464:
440:
432:
429:
421:
413:
405:
386:
382:
378:
357:
344:
324:
314:
295:
290:
288:
284:
280:
276:
272:
266:
264:
261:
257:
256:road networks
253:
249:
245:
241:
237:
236:
227:
191:
163:
155:
152:
144:
136:
128:
110:
108:
105:
101:
97:
93:
88:
85:
81:
78:
74:
70:
67:
63:
58:
54:
48:
43:
37:
33:
19:
6343:Local search
6289:EdmondsâKarp
6256:
6245:BellmanâFord
6015:minimization
5847:GaussâNewton
5797:QuasiâNewton
5782:Trust region
5690:Optimization
5585:
5581:BellmanâFord
5470:
5400:
5362:David Parnas
5337:Shlomi Dolev
5218:
5211:
5204:
5197:
5190:
5183:
5176:
5169:
5162:
5155:
5148:
5141:
5133:
5125:
5117:
5109:
5101:
5093:
4994:
4990:
4961:
4957:
4933:(2): 81â87.
4930:
4926:
4905:1721.1/47994
4887:
4883:
4859:
4853:
4841:
4819:(1): 65â73.
4816:
4810:
4783:
4779:
4747:
4713:
4707:
4675:
4637:
4614:
4608:
4585:
4579:
4567:
4563:
4550:
4525:
4521:
4511:
4502:
4496:
4471:
4467:
4454:
4449:
4428:
4392:
4370:
4357:
4350:
4337:
4329:
4323:
4311:
4282:
4276:
4268:
4263:
4251:. Retrieved
4244:the original
4223:
4219:
4206:
4198:
4194:
4185:
4173:
4166:
4158:the original
4153:
4144:
4131:. Retrieved
4127:the original
4121:
4065:
4059:
4024:
4020:
4014:
3987:
3974:
3950:. Springer.
3947:
3883:
3879:
3866:
3844:(8): 41â47.
3841:
3837:
3817:
3810:. Retrieved
3805:
3795:
3753:
3749:
3738:
3676:
3572:
3527:
3526:
3522:
3517:
3511:
3499:
3493:
3478:
3473:A* algorithm
3470:
3457:graph theory
3452:
3442:
3427:
3423:
2997:bucket queue
2988:
2966:
2943:
2939:
2931:A* algorithm
2924:
2917:
2913:
2899:
2896:
2892:
2888:
2885:
2881:
2877:
2873:
2870:
2867:
2864:
2860:
2856:
2853:
2849:
2845:
2842:
2838:
2835:
2831:
2827:
2821:
2818:
2814:
2599:decrease-key
2598:
2591:average case
2588:
2443:
2343:pairing heap
2291:
2178:
2169:
2166:decrease-key
2165:
2099:
1995:
1810:
1807:Running time
1795:to any node
1790:
1755:
1740:
1635:
1566:
1561:
1560:
1553:
1548:
1547:
1502:
1501:
1490:
1481:
1477:is not empty
1474:
1471:
1464:
1461:
1455:
1444:
1440:
1437:
1422:
1419:
1414:
1412:
1407:
1403:
1399:
1395:
1391:
1387:
1383:
1380:
1376:
1372:
1368:
1364:
1360:
1356:
1352:
1351:16
1348:
1344:
1340:
1339:15
1336:
1332:
1329:
1325:
1321:
1317:
1313:
1310:
1306:
1302:
1298:
1294:
1290:
1286:
1282:
1278:
1274:
1270:
1264:Brodal queue
1245:
1172:
1151:
1147:
1143:
1139:
1136:
1132:
1128:
1124:
1121:
1117:
1113:
1109:
1106:
1102:
1098:
1094:
1090:
1051:
1046:
1042:
1038:
1034:
1031:
1027:
1023:
1019:
1015:
1011:
1007:
1003:
999:
995:
994:â vertex in
991:
987:
984:
980:
976:
972:
968:
964:
960:
956:
952:
944:
940:
936:
935:with a node
932:
928:
856:Graph.Edges(
833:
827:
823:
822:on the path
819:
789:
780:
775:
772:
766:
753:
749:
747:
742:
738:
734:
730:
726:
722:
718:
713:between two
710:
708:
703:
699:
695:
691:
687:
684:intersection
683:
679:
659:
655:
651:
647:
635:
631:
627:
620:
608:
604:
599:
597:
593:
591:
542:
515:
494:
483:
291:
267:
189:
188:
56:
52:
36:
6363:Tabu search
5774:Convergence
5745:Line search
5499:Beam search
5465:αâÎČ pruning
5309:development
4927:SIGACT News
4850:Knuth, D.E.
4685:McGrawâHill
4267:V. JarnĂk:
4133:12 February
3886:: 269â271.
3197:Thorup 2000
2339:binary heap
1733:to at most
1700:is at most
1613:nodes. Let
1493:correctness
1469:inside the
1431:becomes an
1427:block, the
1410:dist, prev
1201:connect to
1142:6
1116::
1049:dist, prev
1045:18 19
723:destination
675:Description
107:performance
6395:Categories
6194:algorithms
5702:heuristics
5694:Algorithms
5586:Dijkstra's
5347:Tony Hoare
4862:(1): 1â5.
4652:References
4075:2204.13547
4034:1810.04481
3812:16 October
3760:below part
3756:: 599â620.
3528:Problem 2.
3267:) runs in
3265:Raman 1997
3199:) runs in
3121:radix heap
1993:may hold.
1297:6 7
792:pseudocode
786:Pseudocode
758:relabeling
663:shortest).
461:. This is
283:subroutine
104:Worst-case
6149:Paradigms
6048:quadratic
5765:Gradients
5727:Functions
5629:Kruskal's
5624:BorĆŻvka's
5596:Johnson's
5401:Wikiquote
5013:207654795
4681:MIT Press
4427:(2009) .
4332:< dist
4102:248427020
3910:123284777
3888:CiteSeerX
3679:Bellman's
3396:ε
3371:
3357:ε
3322:
3235:
3229:
3171:
3097:
3091:
2993:Dial 1969
2828:procedure
2774:
2734:
2631:
2609:Θ
2555:
2517:Θ
2474:
2452:Θ
2413:
2369:Θ
2251:Θ
2203:Θ
2064:⋅
2030:⋅
2011:Θ
1549:Base case
1425:< dist
1355:neighbor
1273:Dijkstra(
1014:still in
1006:neighbor
955:Dijkstra(
731:unlabeled
586:heuristic
582:wavefront
564:Algorithm
530:Amsterdam
522:Groningen
518:Rotterdam
433:
395:Θ
304:Θ
240:algorithm
156:
118:Θ
6380:Software
6257:Dijkstra
6088:exchange
5886:Hessians
5852:Gradient
5519:Parallel
4949:18031586
4833:14986297
4774:(1987).
4746:(1984).
4468:Computer
4193:(1983),
4051:52958911
3939:(2008).
3874:(1959).
3858:27009702
3688:See also
3520:method.
3518:Reaching
2861:for each
1879:, using
1353:for each
1299:for each
1285:5
1271:function
1004:for each
965:for each
953:function
820:next-hop
727:infinity
658:through
536:â
345:, where
246:between
238:) is an
6223:Kruskal
6213:BorĆŻvka
6203:Minimum
5940:General
5698:methods
5328:Related
4978:5221089
4914:5499589
4802:7904683
4732:6754003
4542:1661292
4528:: 2.1.
4488:7301753
4336:dist â
4253:18 July
4228:Bibcode
4150:"ARMAC"
3819:cities?
3512:From a
2886:else if
2502:. The
1467:== dist
1301:vertex
1120:4
967:vertex
854:value.
767:visited
511:History
6085:Basis-
6043:Linear
6013:Convex
5857:Mirror
5814:L-BFGS
5700:, and
5634:Prim's
5457:Search
5330:people
5138:(book)
5130:(book)
5122:(book)
5114:(book)
5106:(book)
5098:(book)
5011:
4976:
4947:
4912:
4831:
4800:
4730:
4691:
4625:
4596:
4540:
4486:
4437:
4400:
4299:
4100:
4090:
4049:
4002:
3962:
3908:
3890:
3856:
3481:greedy
3416:time.
2857:return
2846:return
2189:matrix
2100:where
1793:source
1770:source
1751:source
1745:, the
1666:source
1646:source
1627:source
1556:source
1531:source
1515:source
1479:loop.
1415:source
1408:return
1318:source
1291:source
1279:source
1222:source
1210:target
1204:target
1198:source
1182:target
1176:source
1167:target
1161:source
1114:source
1099:target
1083:target
1077:source
1071:target
1061:target
1055:source
1047:return
961:source
887:source
814:. The
801:source
750:update
721:and a
696:vertex
554:JarnĂk
235:-strÉz
6284:Dinic
6192:Graph
5606:Yen's
5444:Graph
5252:areas
5086:Works
5009:S2CID
4974:S2CID
4945:S2CID
4910:S2CID
4880:(PDF)
4829:S2CID
4798:S2CID
4728:S2CID
4560:(PDF)
4538:S2CID
4484:S2CID
4464:(PDF)
4362:(PDF)
4247:(PDF)
4216:(PDF)
4178:(PDF)
4098:S2CID
4070:arXiv
4047:S2CID
4029:arXiv
3984:(PDF)
3944:(PDF)
3906:S2CID
3854:S2CID
3730:Notes
3438:IS-IS
2933:(see
2349:as a
2345:, or
1472:while
1330:while
1275:Graph
1122:while
985:while
957:Graph
704:graph
680:Note:
574:robot
275:IS-IS
252:graph
248:nodes
87:Graph
65:Class
6250:SPFA
6218:Prim
5812:and
5563:SSS*
5487:SMA*
5482:LPA*
5477:IDA*
5448:tree
5446:and
5307:and
4752:IEEE
4689:ISBN
4683:and
4623:ISBN
4594:ISBN
4435:ISBN
4398:ISBN
4297:ISBN
4255:2017
4135:2015
4088:ISBN
4000:ISBN
3960:ISBN
3814:2017
3758:and
3550:and
3500:The
3471:The
3436:and
3434:OSPF
2951:and
2878:then
2854:then
2843:then
2292:For
2168:and
2132:and
1801:dist
1766:dist
1747:dist
1731:dist
1710:dist
1706:dist
1702:dist
1698:dist
1678:dist
1672:via
1662:dist
1660:and
1658:dist
1652:and
1623:dist
1619:dist
1543:dist
1539:dist
1527:dist
1511:dist
1269:1
1254:and
1231:prev
1227:prev
1219:and
1195:and
1187:prev
1179:and
1058:and
872:and
852:dist
824:from
816:prev
806:dist
796:dist
739:zero
702:and
700:edge
690:and
688:road
558:Prim
343:time
279:OSPF
233:DYKE
96:heap
55:and
6180:cut
6045:and
4999:doi
4966:doi
4935:doi
4900:hdl
4892:doi
4864:doi
4821:doi
4788:doi
4756:doi
4718:doi
4530:doi
4476:doi
4338:alt
4287:doi
4236:doi
4080:doi
4039:doi
3992:doi
3952:doi
3898:doi
3846:doi
3653:to
3613:to
3368:log
3319:log
3310:min
3232:log
3226:log
3168:log
3094:log
3088:log
2771:log
2731:log
2628:log
2552:log
2471:log
2410:log
2187:or
1917:is
1772:to
1692:to
1684:to
1668:to
1648:to
1629:to
1533:to
1517:to
1423:alt
1404:alt
1392:alt
1384:alt
1369:alt
1359:of
1305:in
1262:or
1225:to
1164:to
1101:3
1089:1
1080:to
1039:alt
1035:alt
1020:alt
1010:of
979:to
971:in
951:1
939:in
917:alt
881:alt
754:sum
692:map
617:set
607:to
520:to
430:log
153:log
94:or
6397::
5696:,
5692::
5543:D*
5526:B*
5471:A*
5039:,
5029:,
5007:.
4995:46
4993:.
4989:.
4972:.
4962:30
4960:.
4943:.
4931:28
4929:.
4925:.
4908:.
4898:.
4888:37
4886:.
4882:.
4858:.
4827:.
4817:32
4815:.
4796:.
4784:34
4782:.
4778:.
4770:;
4742:;
4726:.
4714:12
4712:.
4706:.
4669:;
4665:;
4661:;
4621:.
4617:.
4592:.
4568:35
4566:.
4562:.
4536:.
4526:15
4524:.
4520:.
4482:.
4472:16
4470:.
4466:.
4457::
4423:;
4412:^
4386:;
4382:;
4378:;
4295:.
4234:.
4224:36
4222:.
4218:.
4152:.
4109:^
4096:,
4086:,
4078:,
4045:.
4037:.
4025:11
4023:.
3998:.
3986:.
3958:.
3946:.
3935:;
3918:^
3904:.
3896:.
3882:.
3878:.
3852:.
3842:53
3840:.
3826:^
3816:.
3804:.
3781:^
3767:^
3754:35
3752:.
3748:.
3673:.
3570:.
3468:.
3432:,
2922:.
2871:if
2868:do
2850:if
2839:if
2836:do
2832:is
2341:,
2337:,
2289:.
1788:.
1764:,
1633:.
1564::
1551::
1525:,
1509:,
1462:if
1443:â
1420:if
1402:,
1381:if
1375:,
1343:â
1316:â
1311:if
1277:,
1250:,
1238:.
1112:=
1107:or
1103:if
1097:â
1069:=
1032:if
1026:,
959:,
920:.
860:,
828:to
794:,
698:,
686:,
507:.
379:.
289:.
205:aÉȘ
6178:/
5682:e
5675:t
5668:v
5436:e
5429:t
5422:v
5070:e
5063:t
5056:v
5015:.
5001::
4980:.
4968::
4951:.
4937::
4916:.
4902::
4894::
4870:.
4866::
4860:6
4835:.
4823::
4804:.
4790::
4762:.
4758::
4734:.
4720::
4697:.
4631:.
4602:.
4544:.
4532::
4490:.
4478::
4443:.
4406:.
4330:p
4318:.
4289::
4257:.
4238::
4230::
4137:.
4082::
4072::
4053:.
4041::
4031::
4008:.
3994::
3968:.
3954::
3912:.
3900::
3884:1
3860:.
3848::
3762:.
3661:R
3641:P
3621:Q
3601:P
3581:R
3558:Q
3538:P
3453:s
3404:)
3401:}
3393:+
3390:4
3386:/
3382:1
3378:)
3374:C
3365:(
3362:,
3354:+
3351:3
3347:/
3343:1
3339:)
3334:|
3330:V
3326:|
3316:(
3313:{
3306:|
3302:V
3298:|
3294:+
3290:|
3286:E
3282:|
3278:(
3275:O
3251:)
3247:|
3243:V
3239:|
3222:|
3218:E
3214:|
3210:(
3207:O
3191:(
3179:)
3174:C
3162:|
3158:V
3154:|
3150:+
3146:|
3142:E
3138:|
3134:(
3131:O
3115:(
3103:)
3100:C
3084:|
3080:E
3076:|
3072:(
3069:O
3045:)
3042:C
3038:|
3034:V
3030:|
3026:+
3022:|
3018:E
3014:|
3010:(
3007:O
2991:(
2975:C
2953:t
2949:s
2944:t
2942:â
2940:s
2920:)
2918:b
2916:(
2914:O
2909:b
2905:Δ
2900:C
2893:n
2889:n
2882:n
2874:n
2865:n
2795:.
2791:)
2786:|
2782:V
2778:|
2764:|
2760:V
2756:|
2749:|
2745:E
2741:|
2727:|
2723:V
2719:|
2715:+
2711:|
2707:E
2703:|
2698:(
2694:O
2671:)
2668:)
2664:|
2660:V
2656:|
2651:/
2646:|
2642:E
2638:|
2634:(
2624:|
2620:V
2616:|
2612:(
2574:.
2571:)
2567:|
2563:V
2559:|
2548:|
2544:V
2540:|
2536:+
2532:|
2528:E
2524:|
2520:(
2490:)
2486:|
2482:V
2478:|
2467:|
2463:E
2459:|
2455:(
2429:)
2425:|
2421:V
2417:|
2407:)
2403:|
2399:V
2395:|
2391:+
2387:|
2383:E
2379:|
2375:(
2372:(
2356:Q
2319:2
2314:|
2309:V
2305:|
2277:)
2272:2
2267:|
2262:V
2258:|
2254:(
2248:=
2245:)
2240:2
2235:|
2230:V
2226:|
2222:+
2218:|
2214:E
2210:|
2206:(
2193:Q
2181:Q
2174:Q
2149:m
2146:e
2141:T
2117:k
2114:d
2109:T
2085:,
2082:)
2076:m
2073:e
2068:T
2060:|
2056:V
2052:|
2048:+
2042:k
2039:d
2034:T
2026:|
2022:E
2018:|
2014:(
1998:Q
1980:|
1976:E
1972:|
1951:)
1946:2
1941:|
1936:V
1932:|
1928:(
1925:O
1904:|
1900:E
1896:|
1885:Q
1866:|
1862:V
1858:|
1836:|
1832:E
1828:|
1817:V
1813:E
1797:v
1786:u
1782:u
1778:u
1774:w
1762:w
1758:u
1743:v
1737:.
1727:w
1719:w
1712:.
1694:u
1690:w
1686:u
1682:w
1674:w
1670:u
1654:w
1650:u
1642:w
1631:u
1615:u
1601:1
1598:+
1595:k
1575:k
1535:u
1523:u
1519:v
1507:v
1475:Q
1465:p
1456:p
1445:Q
1441:u
1400:v
1396:Q
1388:u
1377:v
1373:u
1361:u
1357:v
1345:Q
1341:u
1333:Q
1314:v
1303:v
1287:Q
1216:r
1192:r
1155:S
1144:u
1137:S
1133:u
1125:u
1110:u
1095:u
1091:S
1067:u
1043:u
1028:v
1024:u
1016:Q
1012:u
1008:v
1000:Q
996:Q
992:u
988:Q
981:Q
977:v
969:v
947:.
945:v
941:Q
937:u
933:v
929:u
911:v
905:v
899:u
893:v
875:v
869:u
864:)
862:v
858:u
847:Q
841:u
834:Q
811:u
660:A
656:B
652:B
648:A
638:.
636:N
632:N
623:.
609:N
600:N
449:)
445:|
441:V
437:|
426:|
422:V
418:|
414:+
410:|
406:E
402:|
398:(
362:|
358:V
354:|
330:)
325:2
320:|
315:V
311:|
307:(
226:/
223:z
220:É
217:r
214:t
211:s
208:k
202:d
199:Ë
196:/
192:(
172:)
168:|
164:V
160:|
149:|
145:V
141:|
137:+
133:|
129:E
125:|
121:(
57:b
53:a
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
