| dbpprop:abstract
|
- Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. An equivalent algorithm was developed by Edward F. Moore in 1957. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
- Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein. Für Graphen mit negativen Gewichten, aber ohne negative Zyklen ist der Bellman-Ford-Algorithmus geeignet. Für nicht-zusammenhängende ungerichtete Graphen kann der Abstand zu bestimmten Knoten auch unendlich sein, wenn ein Pfad zwischen Startknoten und diesen Knoten nicht existiert, dieser aber in der Knotenmenge selbst vorliegt. Dasselbe gilt auch für gerichtete, nicht stark zusammenhängende Graphen.
- 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-Fordův algoritmus. Algoritmus poprvé popsal nizozemský informatik Edsger Dijkstra.
- 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 al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió 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, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo 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).
- Dijkstran algoritmi etsii graafille lyhyimmän polun yhdestä pisteestä kaikkiin muihin pisteisiin. Algoritmi toimii suunnatuilla graafeilla, joiden viivojen painot ovat ei-negatiivisia.
- En théorie des graphes, l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul. L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra et a été publié en 1959. En théorie de la complexité on démontre que cet algorithme est polynomial.
- Fájl:Dijkstra's algorithm. svg A Dijkstra-algoritmus futása egy kis méretű gráfon A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. Az algoritmust Edsger Dijkstra holland informatikus fejlesztette ki. Az algoritmus input egy súlyozott irányított G gráf és p csúcspontja a G gráfnak. A p pont az út kiindulási pontja. Jelöljük V-vel a G gráf csúcspontjainak a halmazát, és legyen (u,v) a G gráf u-t v-vel összekötő éle, ahol u, v a gráf pontjai. Jelöljük E-vel a G gráf éleinek a halmazát. Az élekhez rendelt súlyokat a w: E → [0, ∞) súlyfüggvény adja meg, tehát w(u,v) az u pontból a v pontba való eljutás költsége. Az élekhez rendelt költségeket tekinthetjük a két pont közötti távolság általánosításának. Két pont közötti út költsége az úton lévő élek költségének az összege. Adott s és t V-beli pontpárra az algoritmus megkeresi a legkisebb költségű s-ből t-be vezető utat (azaz a legrövidebb utat). Az algoritmus használható arra is, hogy adott pontból kiindulva a gráf összes többi pontjába vezető legrövidebb utakat megkeressük.
- L'algoritmo di Dijkstra deve il suo nome all'informatico Edsger Dijkstra e permette di trovare i cammini minimi (o Shortest Paths, SP) in un grafo ciclico orientato con pesi non negativi sugli archi: in particolare l'algoritmo può essere utilizzato parzialmente per trovare il cammino minimo che unisce due nodi del grafo, totalmente per trovare quelli che uniscono un nodo d'origine a tutti gli altri nodi o più volte per trovare tutti i cammini minimi da ogni nodo ad ogni altro nodo. Tale algoritmo trova applicazione in molteplici contesti. Per esempio permette, dato un grafo che rappresenta un'ipotetica "mappa" di condotte di approvvigionamento idrico di una città, di calcolare qual è il cammino minimo, e quindi ottimizzare la realizzazione della rete idrica. Esempio analogo può essere fatto considerando il "problema" di trovare il collegamento meno dispendioso, in termini di potenza dissipata, nella realizzazione di un circuito elettrico. Nell'applicare tale algoritmo ai vari campi dello scibile umano, è sicuramente utile affidarsi ad un calcolatore opportunamente istruito con l'algoritmo stesso.
- ファイル:Dijksta Anim. gif ダイクストラ法の動作のアニメーション ダイクストラ法はグラフ理論における最短経路問題を解くためのアルゴリズムである。
- Het kortstepadalgoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. Gegeven een gerichte graaf <math>G</math> waarin de afstand tussen ieder tweetal verbonden punten van <math>G</math> ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop <math>g_b \in G</math> de kortste afstand uit tot alle punten van <math>G</math>. Toepassingen van dit algoritme zijn onder meer bij verkeersmodellen, route-navigatiesystemen en telecommunicatie.
- Dijkstras algoritme er en algoritme for å finne korteste vei i en graf, først publisert av Edsger Dijkstra, og kjent fra flere anvendelser i informatikk og datakommunikasjon. Det forutsettes en graf G=(E, V) der V er mengden noder, og E er grafens enveis (rettede) linker mellom noder. Kostnaden med å gå fra node i til j er linkkost (i, j), og kan ikke være negativ, samt vil være uendelig (∞) der det ikke finnes direkte link. Har man negative linkkostnader kan man bruke Bellman-Ford istedet for Dijkstra. En korteste vei i antall hopp finnes ved å sette linkkost (i, j) = 1 der direkte link finnes, og er kjent brukt ved ruting av informasjon i Internettet. Dijkstra er en grådig algoritme, og mye lik Prims algoritme for å finne et minimalt spenntre. For å finne korteste vei fra utgangspunkt til alle andre noder, vil mengden UFERDIG inneholde noder som ikke er avklart. UFERDIG bør være sortert på hittil laveste sumkost, slik at det er greit å finne den noden som ligger nærmest utgangspunkt, hva kostnad angår. Initielt sumkost(i) = ∞ (uendelig høy) og forrige (i) = null (ingen) for alle noder i i G sumkost(utgangspunkt) = 0 legg alle nodene i UFERDIG Sålenge det ligger noe i UFERDIG sett i til den i UFERDIG som har lavest sumkost fjern i fra UFERDIG for hver UFERDIGE node j der er rimeligere å gå til j via i sett sumkost(j) = sumkost(i) + linkkost(i, j) sett forrige(j) = i Avslutningsvis rimeligste vei fra utgangspunkt til node i er sumkost(i) rimeligste vei til i avdekkes med den rekursive skrivut_vei (i) skrivut_vei (k) : hvis (k er i G) returner skrivut_vei (forrige) pluss k Kjøretiden er lineær i antall noder og kanter, men avhenger av måten man representerer linkkostnader og mengden UFERDIG (en prioritetskø er vanligst).
- 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. Jest często używany w trasowaniu. Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków. Łatwo zmodyfikować go tak, aby szukał wyłącznie ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego. Algorytm Dijkstry jest przykładem algorytmu zachłannego.
- O algoritmo de Dijkstra, cujo nome se origina de seu inventor, o cientista da computação Edsger Dijkstra, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O(log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford. 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?
- Algoritmul lui Dijsktra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf. Numele este dat de Edsger Dijkstra, savantul care l-a descoperit.
- Dijkstras algoritm är en matematisk algoritm för att hitta den 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 upptäckte den år 1959. Den är en girig algoritm som systematiskt löser Bellmans ekvationer, som utgör optimalitetsvillkoren för ett billigast väg-problem: y_j = \min_{i:\left(i,j\right)\in B} y_i+c_{ij} \qquad j=2,\dots,n \qquad y_1 = 0 Lösningar till problemet med den billigaste vägen behövs inom många områden, exempelvis inom routing för att hitta den kortaste vägen när transportsträckor läggs ut.
- 迪科斯彻算法（Dijkstra）是由荷兰计算机科学家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯彻演算法可以用來找到兩個城市之間的最短路徑。 迪科斯彻演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost）。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。
|
| rdfs:comment
|
- Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. An equivalent algorithm was developed by Edward F. Moore in 1957. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e.
- Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen. Die Gewichte dürfen dabei nicht negativ sein. Für Graphen mit negativen Gewichten, aber ohne negative Zyklen ist der Bellman-Ford-Algorithmus geeignet.
- 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).
- 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 al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
- Dijkstran algoritmi etsii graafille lyhyimmän polun yhdestä pisteestä kaikkiin muihin pisteisiin. Algoritmi toimii suunnatuilla graafeilla, joiden viivojen painot ovat ei-negatiivisia.
- En théorie des graphes, l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul. L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra et a été publié en 1959.
- Fájl:Dijkstra's algorithm. svg A Dijkstra-algoritmus futása egy kis méretű gráfon A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva. Az algoritmust Edsger Dijkstra holland informatikus fejlesztette ki. Az algoritmus input egy súlyozott irányított G gráf és p csúcspontja a G gráfnak. A p pont az út kiindulási pontja.
- L'algoritmo di Dijkstra deve il suo nome all'informatico Edsger Dijkstra e permette di trovare i cammini minimi (o Shortest Paths, SP) in un grafo ciclico orientato con pesi non negativi sugli archi: in particolare l'algoritmo può essere utilizzato parzialmente per trovare il cammino minimo che unisce due nodi del grafo, totalmente per trovare quelli che uniscono un nodo d'origine a tutti gli altri nodi o più volte per trovare tutti i cammini minimi da ogni nodo ad ogni altro nodo.
- ファイル:Dijksta Anim. gif ダイクストラ法の動作のアニメーション ダイクストラ法はグラフ理論における最短経路問題を解くためのアルゴリズムである。
- Het kortstepadalgoritme, ook bekend als Dijkstra's algoritme, is een graaf-algoritme beschreven door Edsger Dijkstra in 1959. Gegeven een gerichte graaf <math>G</math> waarin de afstand tussen ieder tweetal verbonden punten van <math>G</math> ten minste 0 bedraagt, rekent het algoritme voor een bepaalde beginknoop <math>g_b \in G</math> de kortste afstand uit tot alle punten van <math>G</math>.
- Dijkstras algoritme er en algoritme for å finne korteste vei i en graf, først publisert av Edsger Dijkstra, og kjent fra flere anvendelser i informatikk og datakommunikasjon. Det forutsettes en graf G=(E, V) der V er mengden noder, og E er grafens enveis (rettede) linker mellom noder. Kostnaden med å gå fra node i til j er linkkost (i, j), og kan ikke være negativ, samt vil være uendelig (∞) der det ikke finnes direkte link.
- 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. Jest często używany w trasowaniu. Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków.
- O algoritmo de Dijkstra, cujo nome se origina de seu inventor, o cientista da computação Edsger Dijkstra, soluciona o problema do caminho mais curto num grafo dirigido ou não dirigido com arestas de peso não negativo, em tempo computacional O(log n) onde m é o número de arestas e n é o número de vértices. O algoritmo que serve para resolver o mesmo problema em um grafo com pesos negativos é o algoritmo de Bellman-Ford.
- Algoritmul lui Dijsktra este o metodă de a stabili drumul de cost minim de la un nod de start la oricare altul dintr-un graf. Numele este dat de Edsger Dijkstra, savantul care l-a descoperit.
- Dijkstras algoritm är en matematisk algoritm för att hitta den 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 upptäckte den år 1959.
|
![[RDF Data]](/statics/sw-cube.png)
