Dijkstra's algorithm (original) (raw)
Dijkstrův algoritmus je algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno převést). Pro grafy s hranami se záporným ohodnocením se obvykle používá pomalejší Bellmanův–Fordův algoritmus. Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra.
| Property | Value |
|---|---|
| dbo:abstract | L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme de cerca de camins per determinar el camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom li ve d'Edsger Dijkstra, qui el va descriure per primera vegada el 1959. La idea subjacent en aquest algorisme consisteix a anar explorant tots els camins més curts que parteixen del vèrtex origen i que porten a tots els altres vèrtexs, quan s'obté el camí més curt des del vèrtex origen, a la resta de vèrtexs que formen el graf, l'algorisme s'atura. L'algorisme és una especialització de la cerca de cost uniforme, i com a tal, no funciona en grafs amb arestes de cost negatiu (a l'hora de triar sempre el node amb distància menor, poden quedar exclosos de la cerca nodes que en properes iteracions baixarien el cost general del camí al passar per una aresta amb cost negatiu). (ca) Dijkstrův algoritmus je algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno převést). Pro grafy s hranami se záporným ohodnocením se obvykle používá pomalejší Bellmanův–Fordův algoritmus. Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra. (cs) خوارزمية ديكسترا (بالإنجليزية: Dijkstra's algorithm) هي خوارزمية تعنى بحل مسألة إيجاد المسار الأقصر بين عقدتين في بيان لا يحتوي على وصلات ذات أوزان سلبية. الخوارزمية مفيدة في عدة تطبيقات، مثل إيجاد الطريق الأقصر بين مدينتين ضمن خريطة، حيث قد تمثل أوزان الوصلات طول الشارع أو مستوى الازدحام في ذلك الشارع أو مجموعهما أو أي معيار مناسب آخر. واضع هذه الخوارزمية هو الهولندي ادسخر دكسترا سنة 1959. (ar) Ο αλγόριθμος του Ντάικστρα πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Ντάικστρα είναι . Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των ή των . Ο αλγόριθμος του Ντάικστρα είναι πλέον ευρέως διαδεδομένος και χρησιμοποιείται σε πολλές εφαρμογές. Χρήση του αλγόριθμου αυτού κάνει το πρωτόκολλο OSPF, το οποίο είναι το του Διαδικτύου. (el) Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem kantengewichteten Graphen (sofern dieser keine Negativkanten enthält). Für unzusammenhängende ungerichtete Graphen ist der Abstand zu denjenigen Knoten unendlich, zu denen kein Pfad vom Startknoten aus existiert. Dasselbe gilt auch für gerichtete nicht stark zusammenhängende Graphen. Dabei wird der Abstand synonym auch als Entfernung, Kosten oder Gewicht bezeichnet. (de) Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A widely used application of shortest path algorithms is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in other algorithms such as Johnson's. The Dijkstra algorithm uses labels that are positive integers or real numbers, which are totally ordered. It can be generalized to use any labels that are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. This generalization is called the generic Dijkstra shortest-path algorithm. Dijkstra's algorithm uses a data structure for storing and querying partial solutions sorted by distance from the start. While the original algorithm uses a min-priority queue and runs in time (where is the number of nodes and is the number of edges), it can also be implemented in using an array. The idea of this algorithm is also given in . propose using a Fibonacci heap min-priority queue to optimize the running time complexity to . This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs 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 Specialized variants. Additionally, if preprocessing is allowed algorithms such as contraction hierarchies can be up to seven orders of magnitude faster. In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as uniform cost search and formulated as an instance of the more general idea of best-first search. (en) Grafo teorian, Dijkstraren algoritmoa, Edsger Dijkstra informatikariak asmatua 1959. urtean, haztapen positiboak (kostuak, distantziak, esaterako) dituen grafo bateko puntu edo erpinen ezberdinen arteko ibilbide hobezina aurkitzeko algoritmoa da. Jatorritzat hartzen den puntu edo erpin batetik abiaturik, algoritmoak grafoko beste puntu edo erpin guztietarako kostu edo distantzia txikiena duen ibilbidea ematen du. Dijkstra-ren algoritmoa algoritmo irenskorra da, pauso bakoitzean kostu edo distantzia txikiena duen ibilbidea aukeratzen baitu. (eu) El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. Su nombre alude a Edsger Dijkstra, científico de la computación de los Países Bajos que lo concibió en 1956 y lo publicó por primera vez en 1959. La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen hasta el resto de los vértices que componen el grafo, el algoritmo se detiene. Se trata de una especialización de la búsqueda de costo uniforme y, como tal, no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).[cita requerida] Una de sus aplicaciones más importantes reside en el campo de la telemática. Gracias a él, es posible resolver grafos con muchos nodos, lo que sería muy complicado resolver sin dicho algoritmo, encontrando así las rutas más cortas entre un origen y todos los destinos en una red.[cita requerida] (es) En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959. Cet algorithme est de complexité polynomiale. Plus précisément, pour sommets et arcs, le temps est en , voire en . (fr) Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot garis (edge weights) yang bernilai nonnegatif, . Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) dan sebuah titik asal dalam himpunan garis . Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik dan dalam , algoritme ini menghitung jarak terpendek dari ke . (in) L'algoritmo di Dijkstra è un algoritmo utilizzato per cercare i cammini minimi in un grafo con o senza ordinamento, ciclico e con pesi non negativi sugli archi. Fu inventato nel 1956 dall'informatico olandese Edsger Dijkstra che lo pubblicò successivamente nel 1959. Tale algoritmo trova applicazione in molteplici contesti quale l'ottimizzazione nella realizzazione di reti (idriche, telecomunicazioni, stradali, circuitali, ecc.) o l'organizzazione e la valutazione di percorsi runtime nel campo della robotica. (it) 컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다. 이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 를 만드는 것이다. 그래프에서 주어진 소스 꼭짓점에 대해서, 데이크스트라 알고리즘은 그 노드와 다른 모든 꼭짓점 간의 가장 짧은 경로를 찾는다.:196–206 이 알고리즘은 어떤 한 꼭짓점에서 다른 한 도착점까지 가는 경로를 찾을 때, 그 도착점까지 가는 가장 짧은 경로가 결정되면 멈추는 식으로 사용할 수 있다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다. 따라서 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용된다. 또한 데이크스트라 알고리즘은 같은 알고리즘의 서브루틴으로 채택되었다. 데이크스트라의 원래 알고리즘은 우선순위 큐를 사용하지 않았기 때문에 시간 복잡도가 (는 꼭짓점의 개수이다)이다. 이 알고리즘의 개념은 에서도 사용된다. 최소 우선 큐에 기반한 알고리즘은 피보나치 힙으로 수행되며 시간복잡도는 때문에 (는 변의 개수이다)이다. 이 알고리즘은 알려진 제한 없는 음이 아닌 가중치를 가지는 무작위 유향 그래프에서의 단일 소스 최단 경로 알고리즘 중 으로 가장 빠른 알고리즘이다. 하지만, 특별한 경우(제한이 있는 정수 가중치나 유향 비순환 그래프 등의 경우)에는 다른 으로 개선할 수 있다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다. (ko) ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。 (ja) Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. Gegeven een gewogen graaf waarin de afstand tussen ieder tweetal verbonden punten van ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop de kortste afstand uit tot alle punten van . Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie. (nl) Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi. (pl) O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional onde V é o número de vértices e E é o número de arestas. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra. O algoritmo considera um conjunto S de menores caminhos, iniciado com um vértice inicial I. A cada passo do algoritmo busca-se nas adjacências dos vértices pertencentes a S aquele vértice com menor distância relativa a I e adiciona-o a S e, então, repetindo os passos até que todos os vértices alcançáveis por I estejam em S. Arestas que ligam vértices já pertencentes a S são desconsideradas. Um exemplo prático do problema que pode ser resolvido pelo algoritmo de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual delas oferece uma trajetória de menor caminho? (pt) Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графу до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без ребер від'ємної довжини. (uk) Dijkstras algoritm är en matematisk algoritm för att hitta den kortaste eller billigaste vägen från en given nod till alla andra noder i en viktad och riktad graf med positiva bågkostnader. Algoritmen har fått sitt namn efter Edsger Dijkstra, som utvecklade den år 1959. Den är en algoritm som systematiskt löser . Dijkstras algoritm är lite av ett specialfall när det kommer till algoritmer. I inledande steg är den att liknas vid en girig algoritm som alltid väljer den kortaste vägen mellan två noder. Den avslutas emellertid med att söka igenom hela den genomgångna grafen efter den totalt sett kortaste vägen, vilket gör algoritmen till ett mellanting mellan en girig algoritm och en algoritm som använder sig av dynamisk programmering. Lösningar till problemet med den billigaste vägen behövs inom många områden, exempelvis inom ruttplanering för att hitta den kortaste vägen när transportsträckor läggs ut. Den används också inom webbaserade reseplanerare för kollektivtrafik för att hitta snabbaste vägen. (sv) 戴克斯特拉算法（英語：Dijkstra's algorithm），又译迪杰斯特拉算法，亦可不音譯而稱爲Dijkstra算法，是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题。 该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。 该算法解决了圖 上带权的单源最短路径问题。具体来说，戴克斯特拉算法设置了一顶点集合，在集合中所有的顶点与源点之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点并将加入中。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该演算法可以用来找到两个城市之间的最短路径。 应当注意，绝大多数的戴克斯特拉算法不能有效处理带有负权边的图。 戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是的一个特例。 (zh) Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Dijkstra_Animation.gif?width=300 |
| dbo:wikiPageExternalLink | http://www.diku.dk/~mthorup/PAPERS/sssp.ps.gz http://purl.umn.edu/107247 http://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html https://dspace.mit.edu/bitstream/1721.1/47994/1/fasteralgorithms00sloa.pdf%7Chdl=1721.1/47994%7Chdl-access=free https://dl.acm.org/doi/10.1145/363269.363610 |
| dbo:wikiPageID | 45809 (xsd:integer) |
| dbo:wikiPageLength | 48956 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119394247 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bellman_equation dbr:Prim's_algorithm dbr:Probability_distribution dbr:Rotterdam dbr:Monotonic_function dbr:Bellman–Ford_algorithm dbr:Big-O_notation dbr:Binary_heap dbr:Algorithm dbr:Best,_worst_and_average_case dbr:Best-first_search dbr:Van_Emde_Boas_tree dbr:Vojtěch_Jarník dbr:Depth-first_search dbr:Information_Processing_Letters dbc:Combinatorial_optimization dbc:Search_algorithms dbr:Neighbourhood_(graph_theory) dbr:Robert_Cecil_Martin dbr:Radix_heap dbr:Graph_(data_structure) dbr:Graph_labeling dbr:Consistent_heuristic dbr:Transit_Node_Routing dbr:MIT_Press dbr:Shortest_path_problem dbr:Subroutine dbr:Communications_of_the_ACM dbr:Computer_scientist dbr:Priority_queue dbr:Theoretical_computer_science dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbc:Graph_distance dbc:Routing_algorithms dbr:Bucket_queue dbr:Admissible_heuristic dbc:1959_in_computing dbr:Centrum_Wiskunde_&_Informatica dbr:Time_complexity dbr:Total_order dbr:Dual_linear_program dbr:Heap_(data_structure) dbr:Johnson's_algorithm dbr:Linear_programming dbr:Link-state_routing_protocol dbr:Transportation_Science dbr:A*_search_algorithm dbr:Adjacency_list dbr:Adjacency_matrix dbr:Amsterdam dbr:Dynamic_programming dbr:Edsger_W._Dijkstra dbc:Edsger_W._Dijkstra dbr:Breadth-first_search dbr:Brodal_queue dbr:Parallel_all-pairs_shortest_path_algorithm dbr:Partially_ordered_set dbr:Directed_graph dbr:Fast_marching_method dbr:Floyd–Warshall_algorithm dbr:Graph_(abstract_data_type) dbr:Graph_theory dbr:Groningen dbr:Asymptotic_computational_complexity dbr:Intersection_(road) dbr:Artificial_intelligence dbc:Dutch_inventions dbr:Charles_Babbage_Institute dbr:Bidirectional_search dbr:Triviality_(mathematics) dbr:Reduced_cost dbr:Dijkstra's_algorithm dbr:Fibonacci_heap dbr:Greedy_algorithm dbr:IEEE dbr:Min-priority_queue dbr:Minimum_spanning_tree dbr:Open_Shortest_Path_First dbr:Search_algorithm dbr:Longest_path_problem dbr:Shortest-path_tree dbr:Set_(abstract_data_type) dbr:Vertex_(graph_theory) dbr:Euclidean_shortest_path dbr:IS-IS dbr:Robert_C._Prim dbr:Routing_protocol dbr:Pseudocode dbr:Self-balancing_binary_search_tree dbr:McGraw–Hill dbr:Pairing_heap dbr:Richard_Bellman dbr:A*_algorithm dbr:A-star_algorithm dbr:Contraction_hierarchy dbr:Least-cost_path dbr:OSPF dbr:Sparse_graph dbr:Negative_cycle dbr:Road_network dbr:File:DijkstraDemo.gif dbr:File:Dijkstras_progress_animation.gif |
| dbp:caption | Dijkstra's algorithm to find the shortest path between a and b. 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 when done with neighbors. (en) |
| dbp:class | dbr:Dynamic_programming dbr:Greedy_algorithm dbr:Search_algorithm |
| dbp:data | dbr:Graph_(data_structure) Usually used with Priority queue/Heap for optimization (en) |
| dbp:wikiPageUsesTemplate | dbt:Graph_search_algorithm dbt:= dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Commons_category dbt:Distinguish dbt:Frac dbt:Harv dbt:Hatnote dbt:IPAc-en dbt:Math dbt:Mono dbt:Mvar dbt:Quote dbt:R dbt:Reflist dbt:Respell dbt:Rp dbt:Short_description dbt:Slink dbt:Use_dmy_dates dbt:Harvnb dbt:Infobox_algorithm dbt:Edsger_Dijkstra dbt:Optimization_algorithms |
| dcterms:subject | dbc:Combinatorial_optimization dbc:Search_algorithms dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbc:Graph_distance dbc:Routing_algorithms dbc:1959_in_computing dbc:Edsger_W._Dijkstra dbc:Dutch_inventions |
| rdf:type | owl:Thing yago:WikicatRoutingAlgorithms yago:WikicatSearchAlgorithms yago:Ability105616246 yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Cognition100023271 yago:Creativity105624700 yago:Event100029378 yago:Invention105633385 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatDutchInventions |
| rdfs:comment | Dijkstrův algoritmus je algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem (neohodnocený graf lze však na ohodnocený snadno převést). Pro grafy s hranami se záporným ohodnocením se obvykle používá pomalejší Bellmanův–Fordův algoritmus. Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra. (cs) خوارزمية ديكسترا (بالإنجليزية: Dijkstra's algorithm) هي خوارزمية تعنى بحل مسألة إيجاد المسار الأقصر بين عقدتين في بيان لا يحتوي على وصلات ذات أوزان سلبية. الخوارزمية مفيدة في عدة تطبيقات، مثل إيجاد الطريق الأقصر بين مدينتين ضمن خريطة، حيث قد تمثل أوزان الوصلات طول الشارع أو مستوى الازدحام في ذلك الشارع أو مجموعهما أو أي معيار مناسب آخر. واضع هذه الخوارزمية هو الهولندي ادسخر دكسترا سنة 1959. (ar) Grafo teorian, Dijkstraren algoritmoa, Edsger Dijkstra informatikariak asmatua 1959. urtean, haztapen positiboak (kostuak, distantziak, esaterako) dituen grafo bateko puntu edo erpinen ezberdinen arteko ibilbide hobezina aurkitzeko algoritmoa da. Jatorritzat hartzen den puntu edo erpin batetik abiaturik, algoritmoak grafoko beste puntu edo erpin guztietarako kostu edo distantzia txikiena duen ibilbidea ematen du. Dijkstra-ren algoritmoa algoritmo irenskorra da, pauso bakoitzean kostu edo distantzia txikiena duen ibilbidea aukeratzen baitu. (eu) L'algoritmo di Dijkstra è un algoritmo utilizzato per cercare i cammini minimi in un grafo con o senza ordinamento, ciclico e con pesi non negativi sugli archi. Fu inventato nel 1956 dall'informatico olandese Edsger Dijkstra che lo pubblicò successivamente nel 1959. Tale algoritmo trova applicazione in molteplici contesti quale l'ottimizzazione nella realizzazione di reti (idriche, telecomunicazioni, stradali, circuitali, ecc.) o l'organizzazione e la valutazione di percorsi runtime nel campo della robotica. (it) ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。 (ja) Het kortstepad-algoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. Gegeven een gewogen graaf waarin de afstand tussen ieder tweetal verbonden punten van ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop de kortste afstand uit tot alle punten van . Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie. (nl) Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi. (pl) Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графу до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без ребер від'ємної довжини. (uk) 戴克斯特拉算法（英語：Dijkstra's algorithm），又译迪杰斯特拉算法，亦可不音譯而稱爲Dijkstra算法，是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似廣度优先搜索的方法解决赋权图的单源最短路径问题。 该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。 该算法解决了圖 上带权的单源最短路径问题。具体来说，戴克斯特拉算法设置了一顶点集合，在集合中所有的顶点与源点之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点并将加入中。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该演算法可以用来找到两个城市之间的最短路径。 应当注意，绝大多数的戴克斯特拉算法不能有效处理带有负权边的图。 戴克斯特拉算法在计算机科学的人工智能等领域也被称为均一开销搜索，并被认为是的一个特例。 (zh) Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS. (ru) L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme de cerca de camins per determinar el camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom li ve d'Edsger Dijkstra, qui el va descriure per primera vegada el 1959. (ca) Ο αλγόριθμος του Ντάικστρα πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Ντάικστρα είναι . Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των ή των . (el) Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er berechnet somit einen kürzesten Pfad zwischen dem gegebenen Startknoten und einem der (oder allen) übrigen Knoten in einem kantengewichteten Graphen (sofern dieser keine Negativkanten enthält). (de) Dijkstra's algorithm (/ˈdaɪkstrəz/ DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. (en) El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista. Su nombre alude a Edsger Dijkstra, científico de la computación de los Países Bajos que lo concibió en 1956 y lo publicó por primera vez en 1959. (es) En théorie des graphes, l'algorithme de Dijkstra (prononcé [dɛɪkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée. (fr) Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot garis (edge weights) yang bernilai nonnegatif, . Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) dan sebuah titik asal dalam himpunan garis . (in) 컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다. 이 알고리즘은 변형이 많다. 데이크스트라의 원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 를 만드는 것이다. 어떤 분야, 특히 인공 지능 분야에서, 데이크스트라 알고리즘이나 그 변형은 균일 비용 탐색으로 알려져 있으며 최상 우선 탐색의 일반적인 아이디어의 예시로 공식화되어있다. (ko) O algoritmo de Dijkstra, concebido pelo cientista da computação holandês Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional onde V é o número de vértices e E é o número de arestas. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford, que possui maior tempo de execução que o Dijkstra. (pt) Dijkstras algoritm är en matematisk algoritm för att hitta den kortaste eller billigaste vägen från en given nod till alla andra noder i en viktad och riktad graf med positiva bågkostnader. Algoritmen har fått sitt namn efter Edsger Dijkstra, som utvecklade den år 1959. Den är en algoritm som systematiskt löser . Dijkstras algoritm är lite av ett specialfall när det kommer till algoritmer. I inledande steg är den att liknas vid en girig algoritm som alltid väljer den kortaste vägen mellan två noder. Den avslutas emellertid med att söka igenom hela den genomgångna grafen efter den totalt sett kortaste vägen, vilket gör algoritmen till ett mellanting mellan en girig algoritm och en algoritm som använder sig av dynamisk programmering. (sv) |
| rdfs:label | خوارزمية ديكسترا (ar) Algorisme de Dijkstra (ca) Dijkstrův algoritmus (cs) Dijkstra-Algorithmus (de) Αλγόριθμος του Ντάικστρα (el) Algoritmo de Dijkstra (es) Dijkstraren algoritmo (eu) Dijkstra's algorithm (en) Algorithme de Dijkstra (fr) Algoritma Dijkstra (in) ダイクストラ法 (ja) Algoritmo di Dijkstra (it) 데이크스트라 알고리즘 (ko) Kortstepad-algoritme (nl) Algorytm Dijkstry (pl) Algoritmo de Dijkstra (pt) Алгоритм Дейкстры (ru) Dijkstras algoritm (sv) Алгоритм Дейкстри (uk) 戴克斯特拉算法 (zh) |
| owl:differentFrom | dbr:Dykstra's_projection_algorithm |
| owl:sameAs | freebase:Dijkstra's algorithm yago-res:Dijkstra's algorithm dbpedia-commons:Dijkstra's algorithm wikidata:Dijkstra's algorithm dbpedia-ar:Dijkstra's algorithm dbpedia-bg:Dijkstra's algorithm http://bs.dbpedia.org/resource/Dijkstrin_algoritam dbpedia-ca:Dijkstra's algorithm dbpedia-cs:Dijkstra's algorithm dbpedia-cy:Dijkstra's algorithm dbpedia-da:Dijkstra's algorithm dbpedia-de:Dijkstra's algorithm dbpedia-el:Dijkstra's algorithm dbpedia-es:Dijkstra's algorithm dbpedia-et:Dijkstra's algorithm dbpedia-eu:Dijkstra's algorithm dbpedia-fa:Dijkstra's algorithm dbpedia-fi:Dijkstra's algorithm dbpedia-fr:Dijkstra's algorithm dbpedia-he:Dijkstra's algorithm http://hi.dbpedia.org/resource/डिजक्स्ट्रा_का_अल्गोरिद्म dbpedia-hr:Dijkstra's algorithm dbpedia-hu:Dijkstra's algorithm http://hy.dbpedia.org/resource/Դեքստրայի_ալգորիթմ dbpedia-id:Dijkstra's algorithm dbpedia-it:Dijkstra's algorithm dbpedia-ja:Dijkstra's algorithm dbpedia-ko:Dijkstra's algorithm dbpedia-lmo:Dijkstra's algorithm http://lt.dbpedia.org/resource/Dijkstros_algoritmas http://lv.dbpedia.org/resource/Deikstras_algoritms dbpedia-mk:Dijkstra's algorithm http://mn.dbpedia.org/resource/Дижикстрагийн_алгоритм dbpedia-nl:Dijkstra's algorithm dbpedia-no:Dijkstra's algorithm dbpedia-pl:Dijkstra's algorithm dbpedia-pt:Dijkstra's algorithm dbpedia-ro:Dijkstra's algorithm dbpedia-ru:Dijkstra's algorithm dbpedia-sh:Dijkstra's algorithm dbpedia-simple:Dijkstra's algorithm dbpedia-sk:Dijkstra's algorithm dbpedia-sl:Dijkstra's algorithm dbpedia-sr:Dijkstra's algorithm dbpedia-sv:Dijkstra's algorithm dbpedia-th:Dijkstra's algorithm dbpedia-uk:Dijkstra's algorithm dbpedia-vi:Dijkstra's algorithm dbpedia-zh:Dijkstra's algorithm https://global.dbpedia.org/id/4zzsS |
| prov:wasDerivedFrom | wikipedia-en:Dijkstra's_algorithm?oldid=1119394247&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DijkstraDemo.gif wiki-commons:Special:FilePath/Dijkstra_Animation.gif wiki-commons:Special:FilePath/Dijkstras_progress_animation.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Dijkstra's_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Dijkstra |
| is dbo:wikiPageRedirects of | dbr:SPF_Algorithm dbr:Generalizations_of_Dijkstra's_algorithm dbr:Shortest_Path_First dbr:Uniform-cost_search dbr:Dial's_algorithm dbr:Dijkstra'_algorithm dbr:Dijkstra's_Algorithm dbr:Dijkstras_algorithm dbr:Dykstra's_algorithm dbr:Dijkstra's_algorithm dbr:Djikstra's_Algorithm dbr:Djikstra's_algorithm dbr:Shortest_path_first dbr:Uniform_Cost_Search dbr:Uniform_cost_search dbr:Dijkstra's_algo dbr:Dijkstra's_distance_algorithm dbr:Dijkstra's_shortest_path dbr:Dijkstra's_shortest_path_algorithm dbr:Dijkstra_algo dbr:Dijkstra_algorithm dbr:Dijkstras_Algorithm dbr:Dijkstra’s_Algorithm dbr:Dikjstra's_algorithm dbr:Dikjstras_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Prim's_algorithm dbr:List_of_algorithms dbr:List_of_computer_scientists dbr:MENTOR_routing_algorithm dbr:Private_Network-to-Network_Interface dbr:SPF_Algorithm dbr:Bellman–Ford_algorithm dbr:Branch_and_bound dbr:Any-angle_path_planning dbr:Best-first_search dbr:List_of_Dutch_inventions_and_innovations dbr:List_of_graph_theory_topics dbr:Pathfinding dbr:Reverse-delete_algorithm dbr:Richard_E._Bellman dbr:Cycle_basis dbr:Velvet_assembler dbr:Dungeon_Crawl_Stone_Soup dbr:Incidence_and_Symmetry_in_Design_and_Architecture dbr:List_of_programmers dbr:Multidimensional_network dbr:Proximity_analysis dbr:Timeline_of_algorithms dbr:Eikonal_equation dbr:Generalizations_of_Dijkstra's_algorithm dbr:Glossary_of_artificial_intelligence dbr:GraphHopper dbr:Modular_Mining_Systems dbr:Multi-chassis_link_aggregation_group dbr:Consistent_heuristic dbr:Contraction_hierarchies dbr:Crowd_simulation dbr:Optical_mesh_network dbr:Order_One_Network_Protocol dbr:Load_balancing_(computing) dbr:Shortest_path_problem dbr:Steiner_tree_problem dbr:Clustering_high-dimensional_data dbr:Friction_of_distance dbr:Kruskal's_algorithm dbr:Path_(graph_theory) dbr:Planar_separator_theorem dbr:Priority_queue dbr:Spanning_tree dbr:Micromouse dbr:State_space_search dbr:Bucket_queue dbr:Traffic_flow dbr:Data,_context_and_interaction dbr:Widest_path_problem dbr:Distance dbr:Heap_(data_structure) dbr:Johnson's_algorithm dbr:Link-state_routing_protocol dbr:Link_analysis dbr:Livewire_Segmentation_Technique dbr:A*_search_algorithm dbr:D-ary_heap dbr:Dynamic_programming dbr:Edsger_W._Dijkstra dbr:Numbers_(season_3) dbr:Dijkstra dbr:Farthest-first_traversal dbr:Fast_marching_method dbr:Flood_fill dbr:Floyd–Warshall_algorithm dbr:Graph_theory dbr:Isomap dbr:Journey_planner dbr:Regular_tree_grammar dbr:Monotone_priority_queue dbr:AF-heap dbr:Biological_network_inference dbr:Bitangent dbr:Suurballe's_algorithm dbr:Edge_disjoint_shortest_pair_algorithm dbr:Real-time_path_planning dbr:Dijkstra's_algorithm dbr:Directed_acyclic_graph dbr:Fibonacci_heap dbr:Greedy_algorithm dbr:Greedy_geometric_spanner dbr:Minimum_bottleneck_spanning_tree dbr:OpenLisp dbr:Open_Shortest_Path_First dbr:Search_algorithm dbr:Seam_carving dbr:Routing dbr:Scalable_Source_Routing dbr:Shortest-path_tree dbr:Shortest_Path_First dbr:Semantic_similarity dbr:Uniform-cost_search dbr:Network_bridge dbr:Shortest_Path_Faster_Algorithm dbr:Euclidean_shortest_path dbr:Facility_location_problem dbr:Dial's_algorithm dbr:Dijkstra'_algorithm dbr:Dijkstra's_Algorithm dbr:Dijkstras_algorithm dbr:IEEE_802.1aq dbr:IS-IS dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Robert_C._Prim dbr:Transit_node_routing dbr:Transport_network_analysis dbr:Fisheye_State_Routing dbr:Visibility_graph dbr:Motion_planning dbr:Sorted_array dbr:Yen's_algorithm dbr:Parallel_single-source_shortest_path_algorithm dbr:Shared_Risk_Resource_Group dbr:Rapidly-exploring_random_tree dbr:Segment_protection dbr:Dykstra's_algorithm dbr:Dijkstra's_algorithm dbr:Djikstra's_Algorithm dbr:Djikstra's_algorithm dbr:Shortest_path_first dbr:Uniform_Cost_Search dbr:Uniform_cost_search dbr:Dijkstra's_algo dbr:Dijkstra's_distance_algorithm dbr:Dijkstra's_shortest_path dbr:Dijkstra's_shortest_path_algorithm dbr:Dijkstra_algo dbr:Dijkstra_algorithm dbr:Dijkstras_Algorithm dbr:Dijkstra’s_Algorithm dbr:Dikjstra's_algorithm dbr:Dikjstras_algorithm |
| is rdfs:seeAlso of | dbr:A*_search_algorithm |
| is owl:differentFrom of | dbr:Dykstra's_projection_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Dijkstra's_algorithm |
