[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/dijkstra-algorithmus-wikipedia-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/dijkstra-algorithmus-wikipedia-wikipedia\/","headline":"Dijkstra-Algorithmus \u2013 Wikipedia Wikipedia","name":"Dijkstra-Algorithmus \u2013 Wikipedia Wikipedia","description":"before-content-x4 The Algorithm from Dijkstra (according to his inventor Edsger W. Dijkstra) is an algorithm from the class of the","datePublished":"2021-03-24","dateModified":"2021-03-24","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/5\/57\/Dijkstra_Animation.gif\/220px-Dijkstra_Animation.gif","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/5\/57\/Dijkstra_Animation.gif\/220px-Dijkstra_Animation.gif","height":"173","width":"220"},"url":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/dijkstra-algorithmus-wikipedia-wikipedia\/","wordCount":12333,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4  The Algorithm from Dijkstra (according to his inventor Edsger W. Dijkstra) is an algorithm from the class of the Greedy algorithms [first] And solve the problem of the shortest paths for a given start node. It therefore calculates a shortest path between the given start node and one of the (or all) other knots in an edge -weighted graph (provided that it does not contain any negative edges).        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4For incoherent undemanded graphs, the distance to those nodes is infinite, to which there is no path from the start node. The same also applies to not strongly contiguous graphs. The distance is also synonymously referred to as distance, costs or weight. Informal presentation [ Edit | Edit the source text ] The basic idea of \u200b\u200bthe algorithm is to always follow the edge that promises the shortest section of the route from the start node. Other edges are only pursued when all shorter sections of the route (also beyond other knots) have been observed. This procedure ensures that if a node is reached, no shorter path can exist. A once calculated distance between the start node and a knot visited is saved. The upgraded distances to the nodes that have not yet been processed can change in the course of the algorithm, namely to reduce. This procedure continues until the distance of the target node has been calculated ( single-pair shortest path ) or the distances of all nodes to the start node are known ( single-source shortest path ).  The algorithm can be described by the following steps. Both the shortest (upgraded) distances and their nodes are calculated.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4All nodes the two properties (attributes) “distance” and “predecessor”. Initialize the distance in the start node with 0 and in all other knots \u221e {displaystyle infty } . As long as there are still no -seeking nodes, choose those with a minimal (upgrowed) distance andSave that this knot has already been visited. Calculate the overall distance for all of the neighboring nodes, the total distance of the respective edge weight and the already calculated distance from the start node to the current node. If this value is smaller for a knot than the distance stored there, update it and set the current knot as predecessor.This step is also as Update or Relaxation\/relaxation designated. In this form, the algorithm calculates the shortest ways to all other nodes from a start node. On the other hand, if you are only interested in the way to a very specific node, you can cancel in step (2) if the knot you are looking for is the active.  Negative edge weights can lead to non-optimal solutions. Due to the property of no longer changing distances to the start node, the Dijkstra algorithm is one of the Greedy algorithms, which prefer the most promising partial solution at the moment in every step. Unlike some other Greedy algorithms, the Dijkstra algorithm always calculates an optimal solution. This property is based on the assumption that the shortest sections between knots together form the shortest route on this path together. The assumption is valid on the prerequisite of positive edge weights, because if you would find a shorter way from the start node to a target node, you would have had to examine your shorter section earlier to correctly carry out the algorithm. Then one would have found the target node earlier than on the longer path via the shorter section. However, the assumption no longer applies if the graph contains negative edge weights. Then each section can be a shortest route between the end points, but you could improve the total distance via a longer partial path if a negative edge reduces the length of the path again. In the picture with the nodes 1, 2, 3 and 4, the Dijkstra algorithm would find the shortest way from 1 to 3 via 2, since the step to 4 has been overall than the entire upper path. However, the negative edge causes the lower path to be shorter.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Algorithm in pseudocode [ Edit | Edit the source text ] The following lines of pseudocode describe a function called Dijkstra, which receives a graph and a starting knot in the graph as input. The starting node indicates the knot from which the shortest ways to all the knots are sought. The result is a list for each knot in the previous node on the way from the start node too in indicated. The graph consists of nodes and weighted edges, with the weight of the distance between the knots. If there is an edge between two knots, the knots are neighbors. The node currently considered in the partial step is with in referred to and is called “viewing node”. The possible, coming neighboring nodes are in the respective, upcoming intermediate examination with each in referred to as “test node”. The edge weight between viewing node in and respective test nodes in is in pseudocode as distance_ between (u, v) given. The numerical value of distance [v] In the branch of the examination, contains the respective total removal, which the partial distances from the starting point via possible intermediate nodes and the current nodes in Until the next knot to be examined in added. First of all, the distances and predecessors are initiated depending on the graph and start nodes. This happens in the method initialize . The actual algorithm uses a method distance_update that carries out an update of the distances if a shorter path has been found. first function Dijkstra( Graph , The starter knot ): 2 initialized ( Graph , The starter knot , distance [], predecessor [], Q ) 3 as long as  Q  not file: \/\/ The actual algorithm 4 in : = Knot in Q With the smallest value at a distance [] 5 remove in out of Q  \/\/ for in the shortest way is determined now 6 for each Neighbors in from in : 7 falls  in in Q : \/\/ if not yet calculated 8 distance_update ( in , in , distance [], predecessor []) \/\/ check the distance from the start node too in  9 return predecessor[] The initialization relies on the distances to infinity and the predecessors as unknown. Only the start node has the distance 0. The amount Q Contains the knots to which no shortest way has been found. first Method Initialize (graph, start node, distance [], predecessor [], Q): 2 for each node in in Graph : 3 distance [ in ]: = infinite 4 predecessors [ in ]: = null 5 distance [ The starter knot ]: = 0 6 Q : = All nodes in Graph  The distance from the start node to the knot in If the path is too in above in shorter than the previously known path is. Accordingly in To the predecessor of in On the shortest way. first Method distance_update (u, v, distance [], predecessor []): 2 alternative : = distance [ in ] + distance_ between ( in , in ) \/\/ path length from the start node to V over u 3 falls  alternative first; \/\/ Abstand        int index = vertexQueue.begin()->second;        vertexQueue.erase(vertexQueue.begin()); \/\/ Entfernt den ersten Knoten der Warteschlange        const vector& neighbors = adjacencyList[index];        \/\/ Diese for-Schleife durchl\u00e4uft alle Nachbarn des Knoten mit index        for (vector::const_iterator neighborIterator = neighbors.begin(); neighborIterator != neighbors.end(); neighborIterator++)        {            int targetIndex = neighborIterator->targetIndex; \/\/ Index des Nachbarknotens            string name = neighborIterator->name; \/\/ Name des Nachbarknotens            double weight = neighborIterator->weight; \/\/ Abstand zum Nachbarknoten            double currentDistance = distance + weight; \/\/ Abstand vom Startknoten zum Knoten mit index            if (currentDistance T em) {displaystyle O(|E|cdot T_{mathrm {dk} }+|V|cdot T_{mathrm {em} })} whereby T dk{displaystyle T_{mathrm {dk} }} and T em{displaystyle T_{mathrm {em} }} For the complexity of the decrease-key – and extract-minimum -Perivations at Q {displaystyle Q} stand. The simplest implementation for Q {displaystyle Q} is a list or an array. The time complexity is O ( | AND | + | IN | 2 ) = O ( | IN | 2 ) {Displaystyle o (| E |+| V |^{2}) = O (| V |^{2})} . Normally, you will use a priority queue here by using the nodes there as elements with their respective distant distance as a key\/priority. The optimal term for a graph G = ( IN , AND ) {displaystyle G=(V,E)} amounts to O ( | IN | log \u2061 ( | IN | ) + | AND | ) {Displaystyle O (| V | log (| V |)+| E |)} by using a Fibonacci heap for the Dijkstra algorithm. [5] Route planners are a prominent example in which this algorithm can be used. The graph represents the network of traffic routes, which connects various points. We are looking for the shortest route between two points. Some topological indices, such as the J-index of Balaban, need weighted distances between the atoms of a molecule. In these cases, weighting is the binding regulations. Dijkstras Algorithm is also used on the Internet as a routing algorithm in the OSPF, IS-IS and OLSR protocol. The latter Optimized Link State Routing -Protocol is a version of the Link State Routing adapted to the requirements of a mobile wireless LAN. It is important for mobile ad hoc networks. The free radio networks are possible. The Dijkstra algorithm can also be used when solving the coin problem, a number-theoretical problem that has nothing to do with graphs at first glance. If you have enough information about the edge weights in the graph in order to be able to derive a heuristic for the costs of individual nodes, it is possible to expand Dijkstra’s algorithm to the A*algorithm. In order to calculate all the shortest paths from one knot to all other nodes in a graph, you can also use the Bellman-Ford algorithm, which can handle negative edge weights. The algorithm of Floyd and Warshall finally calculates the shortest paths of all nodes. Thomas H Cormmen, Charles E. Leiseron, Ronald L. Rivest, Clifford Stein: Algorithms – an introduction . Oldenbourg, Munich\/ Vienna 2004, ISBN 3-486-27515-1, S.  598\u2013604 (English: Introduction to algorithms . Translated by Karen Lippert, Micaela Krieger-Hauwede).  Robert Sedgewick: Algorithms in C++ Part 5: Graph Algorithms. Indianapolis 2002, ISBN 0-201-36118-3, S. 293\u20133 Edsger W. Dijkstra: A note on two problems in connexion with graphs. In: Numerical Mathematics. 1, 1959, S. 269\u2013271; ma.tum.de (PDF; 739\u00a0kB). \u2191  Tobias H\u00e4berlein: Practical algorithm with python. Oldenbourg, Munich 2012, ISBN 978-3-486-71390-9, p. 162 ff.  \u2191  Rosetta Code: Dijkstra’s algorithm  \u2191  GeeksforGeeks: Dijkstra\u2019s shortest path algorithm  \u2191  The Simple, Elegant Algorithm That Makes Google Maps Possible. At: VICE. Accessed on October 3, 2020.  \u2191  Thomas H. Cormen: Introduction to Algorithms . With press, S.  663 .        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2en\/wiki6\/dijkstra-algorithmus-wikipedia-wikipedia\/#breadcrumbitem","name":"Dijkstra-Algorithmus \u2013 Wikipedia Wikipedia"}}]}]