|
'''Algoritma Dijkstra''', dinamai menurut penemunya, [[Edsger Dijkstra]], adalah [[greedy algorithm]] yang memecahkan [[shortest path problem]] untuk sebuah [[directed graph]] dengan edge weights yang tidak negatif.
For exampleMisalnya, if thebila [[vertices]] ofdari thesebuah graph representmelambangkan citieskota-kota anddan edge weights representmelambangkan drivingjarak distancesantara betweenkota-kota pairstersebut, of cities connected by a direct road,algoritma Dijkstra's algorithm can be useddapat todigunakan finduntuk themenemukan shortestjarak routeterpendek betweenantara twodua citieskota.
TheInput inputalgoritma ofini theadalah algorithm consists of asebuah weighted directed graph ''G'' anddan asebuah source vertex ''s'' indalam ''G''. We will denote ''V'' theadalah sethimpunan of allsemua [[vertex (graph theory)|vertices]] in thedalam graph ''G''. EachSetiap [[edge (graph theory)|edge]] of thedari graph is an orderedini pairadalah ofpasangan vertices (''u'',''v'') representingyang amelambangkan connectionhubungan fromdari vertex ''u'' toke vertex ''v''. TheHimpunan setsemua of all edges isedge denoteddisebut ''E''. Weights ofdari edges aredihitung givendengan by a weight functionfungsi ''w'': ''E'' → [0, ∞); thereforejadi ''w''(''u'',''v'') isadalah thejarak non-negativenegatif cost of moving directly fromdari vertex ''u'' toke vertex ''v''. TheCost costdari of ansebuah edge candapat bedianggap thoughtsebagai ofjarak asantara (adua generalizationvertex, of)yaitu thejumlah distancejarak betweensemua thoseedge two vertices. The cost of adalam path between two vertices is the sum of costs of the edges in that pathtersebut. ForUntuk asepasang given pair of verticesvertex ''s'' anddan ''t'' indalam ''V'', thealgoritma algorithmini findsmenghitung thejarak pathterpendek fromdari ''s'' toke ''t'' with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex ''s'' to all other vertices in the graph.
==Description of the algorithm==
The algorithm works by keeping for each vertex ''v'' the cost ''d''[''v''] of the shortest path found so far between ''s'' and ''v''. Initially, this value is 0 for the source vertex ''s'' (''d''[''s'']=0), and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices (''d''[''v'']=∞ for every ''v'' in ''V'', except ''s''). When the algorithm finishes, ''d''[''v''] will be the cost of the shortest path from ''s'' to ''v'' — or infinity, if no such path exists.
The basic operation of Dijkstra's algorithm is '''edge relaxation''': if there is an edge from ''u'' to ''v'', then the shortest known path from ''s'' to ''u'' (''d''[''u'']) can be extended to a path from ''s'' to ''v'' by adding edge (''u'',''v'') at the end. This path will have length ''d''[''u'']+''w''(''u'',''v''). If this is less than the current ''d''[''v''], we can replace the current value of ''d''[''v''] with the new value. Edge relaxation is applied until all values ''d''[''v''] represent the cost of the shortest path from ''s'' to ''v''. The algorithm is organised so that each edge (''u'',''v'') is relaxed only once, when ''d''[''u''] has reached its final value.
The notion of "relaxation" comes from an [[analogy]] between the estimate of the shortest path and the length of a [[helix|helical]] tension [[spring (device)|spring]], which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to a stretched out spring. As shorter paths are found, the estimated cost is lowered, and the spring is relaxed. Eventually, the shortest path, if one exists, is found and the spring has been relaxed to its resting length.
The algorithm maintains two sets of vertices ''S'' and ''Q''. Set ''S'' contains all vertices for which we know that the value ''d''[''v''] is already the cost of the shortest path and set ''Q'' contains all other vertices. Set ''S'' starts empty, and in each step one vertex is moved from ''Q'' to ''S''. This vertex is chosen as the vertex with lowest value of ''d''[''u'']. When a vertex ''u'' is moved to ''S'', the algorithm relaxes every outgoing edge (''u'',''v'').
In the following algorithm, u := Extract_Min(Q) searches for the vertex ''u'' in the vertex set ''Q'' that has the least ''d''[''u''] value. That vertex is removed from the set ''Q'' and returned to the user.
1 '''function''' Dijkstra(G, w, s)
2 '''for each''' vertex v in V[G] ''// Initializations''
14 previous[v] := u
== Rujukan ==
If we are only interested in a shortest path between vertices ''s'' and ''t'', we can terminate the search at line 9 if ''u'' = ''t''.
Now we can read the shortest path from ''s'' to ''t'' by iteration:
1 S := empty sequence
2 u := t
3 '''while''' defined previous[u]
4 insert u to the beginning of S
5 u := previous[u]
Now sequence ''S'' is the list of vertices constituting one of the shortest paths from ''s'' to ''t'', or the empty sequence if no path exists.
A more general problem would be to find all the shortest paths between ''s'' and ''t'' (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous[] we would store all nodes satisfying the relaxation condition. For example, if both ''r'' and ''s'' connect to ''t'' and both of them lie on different shortest paths through ''t'' (because the edge cost is the same in both cases), then we would add both ''r'' and ''s'' to previous[t]. When the algorithm completes, previous[] 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 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 short paths between two given nodes we would use path finding algorithm on the new graph, such as depth-first search.
== Running time==
We can express the running time of Dijkstra's algorithm on a graph with ''E'' edges and ''V'' vertices as a function of ''|E|'' and ''|V|'' using the [[Big O notation#Graph Theory|Big-O notation]].
The simplest implementation of the Dijkstra's algorithm stores vertices of set ''Q'' in an ordinary linked list or array, and operation Extract-Min(''Q'') is simply a linear search through all vertices in ''Q''. In this case, the running time is ''O''(''V''<sup>2</sup>).
For [[sparse graph]]s, that is, graphs with much less than ''V''<sup>2</sup> edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of [[adjacency list]]s and using a [[binary heap]] or [[Fibonacci heap]] as a [[priority queue]] to implement the Extract-Min function. With a binary heap, the algorithm requires ''O''((''E''+''V'')log''V'') time, and the Fibonacci heap improves this to ''O''(''E'' + ''V''log''V'').
== Related problems and algorithms ==
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. 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.
OSPF ([[open shortest path first]]) is a well known real-world implementation of Dijkstra's algorithm used in internet [[routing]].
Unlike Dijkstra's algorithm, the [[Bellman-Ford algorithm]] can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex ''s''. (The presence of such cycles means there is no shortest path, since the total weight becomes lower each time the cycle is traversed.)
A related problem is the [[traveling salesman problem]], which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. This problem is [[NP-complete]]; in other words, unlike the shortest path problem, it is unlikely to be solved by a [[Nondeterministic Turing machine|deterministic]] polynomial-time algorithm.
The [[A-star algorithm|A* algorithm]] 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.
==References==
* E. W. Dijkstra: ''A note on two problems in connexion with graphs''. In: ''Numerische Mathematik''. 1 (1959), S. 269–271
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp.595–601.
== SeeLihat alsojuga ==
* [[Breadth-first search]]
* [[Open shortest path first]]
== Pranala luar ==
==External links==
* [http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html]
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html Animation of Dijkstra's algorithm]
* [http://www.boost.org/libs/graph/doc/index.html The Boost Graph Library (BGL)]
* [http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Shortest Path Problem: Dijkstra's Algorithm]
* [http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm Dijkstra's Algorithm Applet]
[[Category:Graph algorithms]]
[[Category:Routing algorithms]]
[[Category:Combinatorial optimization]]
[[bg:Алгоритъм на Дейкстра]]
| 