| dbo:abstract
|
- En teoria de grafs, el problema del camí més curt consisteix a trobar un camí entre dos vèrtexs (o nodes) d'un graf de tal manera que la suma dels pesos de les arestes que el formen sigui mínima. Un exemple és trobar el camí més ràpid per anar d'una ciutat a una altra en un mapa. En aquest cas, els vèrtexs representen les ciutats i les arestes, les carreteres que les uneixen; la ponderació ve donada pel temps que s'empra en viatjar. (ca)
- تهدف مسائل أقصر طريق (بالإنجليزية: Shortest Path Problem) في نظرية المخططات لإيجاد طريق بين رأسين في مخطط بحيث تكون أوزان الأضلاع المكونة له بأقل ما يمكن. (ar)
- Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten eines Graphen, welcher minimale Länge bezüglich einer Kantengewichtsfunktion hat.Haben die Kanten im Graphen alle das Gewicht 1, ist also für alle Kanten , so ist der kürzeste Pfad ein –-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen und . In der Literatur wird das Problem oft als Shortest Path Problem bezeichnet. (de)
- En la teoría de grafos, el problema del camino más corto es el problema que consiste en encontrar un camino entre dos vértices o nodos, de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima. Al camino más corto entre dos vértices también se le conoce como geodésica. Este problema no necesariamente tiene una única solución. Además, tiene diversas aplicaciones. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. (es)
- En théorie des graphes, le problème de plus court chemin est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. (fr)
- Dalam teori graf, masalah lintasan terpendek merupakan masalah yang menanyakan bagaimana mencari sebuah pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut, jika diberikan sebuah graf berbobot. Masalah dari mencari jarak terpendek antara dua persimpangan dari peta jalan (simpul graf yang berhubungan ke persimpangan dan ujung yang behubungan ke segmen jalan, yang tiap-tiap nya diberi bobot oleh panjang dari segmen jalan) dapat dimodelkan dari kasus spesial dari masalah jarak terpendek dalam graf. (in)
- In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment. (en)
- グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 (ja)
- 그래프 이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다. 보통은 주어진 가중 그래프에서 (V는 꼭짓점, E는 변, 가중치 함수 f : E → R) 가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.이런 문제는 단일-쌍 최단 경로 문제라고 부르며, 아래의 일반화된 문제들과는 차이가 있다.
* 단일-출발 최단 경로 문제 : 단일 꼭짓점 v에서 출발하여 그래프 내의 모든 다른 꼭짓점들에 도착하는 가장 짧은 경로를 찾는 문제이다.
* 단일-도착 최단 경로 문제 : 모든 꼭짓점들로부터 출발하여 그래프 내의 한 단일 꼭짓점 v로 도착하는 가장 짧은 경로를 찾는 문제이다. 이 문제에서 그래프 내의 꼭짓점들을 거꾸로 뒤집으면 출발 최단 경로 문제로 바뀔 수 있다.
* 전체-쌍 최단 경로 문제 : 그래프 내의 모든 꼭짓점 쌍들 사이의 최단 경로를 찾는 문제이다. 위의 일반화된 문제들은, 전체-쌍 중 단일-쌍만으로 찾아가는 단순 접근 방식보다, 확실히 더 효율적인 알고리즘을 가진다. (ko)
- Nella teoria dei grafi, il cammino minimo (o shortest path) tra due vertici (o nodi) di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma dei costi associati all'attraversamento di ciascun arco (o lato). (it)
- Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida. Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um conjunto A de arestas e uma função de peso ) e, dado qualquer elemento v de V, encontrar um caminho P de v para cada v' de V tal que é mínimo entre todos os caminhos conectando n a n'. Em programação dinâmica, podemos escolher um subproblema de modo que toda a informação vital seja recordada e levada adiante. Assim, vamos definir que para cada vértice e cada inteiro , como o menor caminho de até que usa arestas. Os valores iniciais de são para todos os vértices exceto , para o qual é 0. E a equação geral de atualização é: Existem várias variantes para problemas de caminho mínimo, cada uma adequada a um conjunto de problemas diferente:
* Problema de único destino: consiste em determinar o menor caminho entre cada um dos nós do grafo e um nó de destino dado.
* Problema de único origem: determinar o menor caminho entre um nó dado e todos os demais nós do grafo.
* Problema de origem-destino: determinar o menor caminho entre nós dados.
* Problemas de todos os pares: determinar o menor caminho entre cada par de nós presentes no grafo. Os algoritmos especializados em solucionar o problema do caminho mínimo são eventualmente chamados de algoritmos de busca de caminhos. Entre os algoritmos dessa classe, os mais conhecidos são:
* Algoritmo de Dijkstra — Resolve o problema com um vértice-fonte em grafos cujas arestas tenham peso maior ou igual a zero. Sem reduzir o desempenho, este algoritmo é capaz de determinar o caminho mínimo, partindo de um vértice de início v para todos os outros vértices do grafo.
* Algoritmo de Bellman-Ford — Resolve o problema para grafos com um vértice-fonte e arestas que podem ter pesos negativos.
* Algoritmo A* — um algoritmo heurístico que calcula o caminho mínimo com um vértice-fonte.
* Algoritmo de Floyd-Warshall — Determina a distância entre todos os pares de vértices de um grafo.
* Algoritmo de Johnson — Determina a distância entre todos os pares de vértices de um grafo, pode ser mais veloz que o algoritmo de Floyd-Warshall em .
* Algoritmo Viterbi — Resolve o menor problema de caminho estocástico com um peso probabilístico adicional em cada nó. (pt)
- Problem najkrótszej ścieżki – zagadnienie w teorii grafów polegające na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków. Okazuje się, że żeby znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami grafu trzeba (w pesymistycznym przypadku) znaleźć najkrótsze ścieżki od wierzchołka wyjściowego do wszystkich innych wierzchołków. Problem najkrótszej ścieżki od jednego z wierzchołków do wszystkich innych można więc zobrazować jako problem znalezienia najkrótszej drogi pomiędzy dwoma miastami. W takim wypadku wierzchołkami grafu są skrzyżowania dróg, krawędziami – drogi, a wagi krawędzi odwzorowują długość danego odcinka drogowego. Do znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami zazwyczaj używane są algorytmy:
* Dijkstry (przy założeniu, że w grafie nie ma wag ujemnych) o pesymistycznej złożoności obliczeniowej
* Bellmana-Forda o pesymistycznej złożoności obliczeniowej
* A*, używający heurystyki,
* wykorzystujący sortowanie topologiczne z relaksacją (dla skierowanych grafów acyklicznych) o pesymistycznej złożoności obliczeniowej gdzie V to liczba wierzchołków grafu, a E to liczba jego krawędzi. Drugi szczególny przypadek problemu najkrótszej ścieżki występuje, gdy chcemy znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków. Możliwe jest zrobienie tego dla każdego wierzchołka, używając algorytmu znajdującego najkrótszą ścieżkę od jednego wierzchołka do wszystkich innych, jednak metoda ta okazuje się w praktyce niezbyt efektywna. Najkrótsze ścieżki pomiędzy wszystkimi wierzchołkami znajdują m.in. algorytmy:
* nienazwany (wykorzystuje mnożenie macierzy) o pesymistycznej złożoności obliczeniowej
* Floyda-Warshalla o pesymistycznej złożoności obliczeniowej
* Johnsona o pesymistycznej złożoności obliczeniowej gdzie V to liczba wierzchołków, a E liczba krawędzi. (pl)
- Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь. Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения. У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе. Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий. (ru)
- В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами — відтинки дороги із вагами, рівними часу, необхідному для подолання цього відрізку. Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E → R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що найменша серед усіх шляхів, що зв'язують v з v' . Така задача іноді згадується як Задача про найкоротший шлях між парою вершин, щоб відрізнити від наступних узагальнень:
* Задача про найкоротші шляхи з одного входу, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графу.
* Задача про найкоротші шляхи з одним виходом, тут ми маємо знайти найкоротші шляхи з усіх вершин графу до однієї вихідної v. Може бути зведена до задачі з одним входом шляхом зміни на зворотні ребер графу.
* Задача про найкоротші шляхи для всіх пар, тут ми маємо знайти найкоротші шляхи між кожною парою вершин v, v' в графі. Ці узагальнення мають значно дієвіші алгоритми ніж спрощений підхід із запуском алгоритму пошуку найкоротшого шляху між всіма значимими парами вершин. (uk)
- 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
* 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。
* 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
* 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
* 全局最短路径问题 - 也叫多源最短路问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
* Dijkstra算法
* A*算法
* Bellman-Ford算法
* SPFA算法（Bellman-Ford算法的改进版本）
* Floyd-Warshall算法
*
* 双向搜索 (zh)
|
| rdfs:comment
|
- En teoria de grafs, el problema del camí més curt consisteix a trobar un camí entre dos vèrtexs (o nodes) d'un graf de tal manera que la suma dels pesos de les arestes que el formen sigui mínima. Un exemple és trobar el camí més ràpid per anar d'una ciutat a una altra en un mapa. En aquest cas, els vèrtexs representen les ciutats i les arestes, les carreteres que les uneixen; la ponderació ve donada pel temps que s'empra en viatjar. (ca)
- تهدف مسائل أقصر طريق (بالإنجليزية: Shortest Path Problem) في نظرية المخططات لإيجاد طريق بين رأسين في مخطط بحيث تكون أوزان الأضلاع المكونة له بأقل ما يمكن. (ar)
- Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei unterschiedlichen Knoten eines Graphen, welcher minimale Länge bezüglich einer Kantengewichtsfunktion hat.Haben die Kanten im Graphen alle das Gewicht 1, ist also für alle Kanten , so ist der kürzeste Pfad ein –-Pfad mit der geringstmöglichen Anzahl von Kanten zwischen und . In der Literatur wird das Problem oft als Shortest Path Problem bezeichnet. (de)
- En théorie des graphes, le problème de plus court chemin est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. (fr)
- Dalam teori graf, masalah lintasan terpendek merupakan masalah yang menanyakan bagaimana mencari sebuah pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut, jika diberikan sebuah graf berbobot. Masalah dari mencari jarak terpendek antara dua persimpangan dari peta jalan (simpul graf yang berhubungan ke persimpangan dan ujung yang behubungan ke segmen jalan, yang tiap-tiap nya diberi bobot oleh panjang dari segmen jalan) dapat dimodelkan dari kasus spesial dari masalah jarak terpendek dalam graf. (in)
- In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment. (en)
- グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 (ja)
- Nella teoria dei grafi, il cammino minimo (o shortest path) tra due vertici (o nodi) di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma dei costi associati all'attraversamento di ciascun arco (o lato). (it)
- 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
* 确定起点的最短路径问题 - 也叫单源最短路问题，即已知起始结点，求最短路径的问题。在边权非负时适合使用Dijkstra算法，若边权为负时则适合使用Bellman-ford算法或者SPFA算法。
* 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
* 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
* 全局最短路径问题 - 也叫多源最短路问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
* Dijkstra算法
* A*算法
* Bellman-Ford算法
* SPFA算法（Bellman-Ford算法的改进版本）
* Floyd-Warshall算法
*
* 双向搜索 (zh)
- En la teoría de grafos, el problema del camino más corto es el problema que consiste en encontrar un camino entre dos vértices o nodos, de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima. Al camino más corto entre dos vértices también se le conoce como geodésica. (es)
- 그래프 이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다. 보통은 주어진 가중 그래프에서 (V는 꼭짓점, E는 변, 가중치 함수 f : E → R) 가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.이런 문제는 단일-쌍 최단 경로 문제라고 부르며, 아래의 일반화된 문제들과는 차이가 있다. 위의 일반화된 문제들은, 전체-쌍 중 단일-쌍만으로 찾아가는 단순 접근 방식보다, 확실히 더 효율적인 알고리즘을 가진다. (ko)
- Problem najkrótszej ścieżki – zagadnienie w teorii grafów polegające na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków. gdzie V to liczba wierzchołków grafu, a E to liczba jego krawędzi. gdzie V to liczba wierzchołków, a E liczba krawędzi. (pl)
- Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou vértices); custo este dado pela soma dos pesos de cada aresta percorrida. Formalmente, dado um grafo valorado (ou seja, um conjunto V de vértices, um conjunto A de arestas e uma função de peso ) e, dado qualquer elemento v de V, encontrar um caminho P de v para cada v' de V tal que é mínimo entre todos os caminhos conectando n a n'. Existem várias variantes para problemas de caminho mínimo, cada uma adequada a um conjunto de problemas diferente: (pt)
- В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами — відтинки дороги із вагами, рівними часу, необхідному для подолання цього відрізку. Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E → R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що (uk)
- Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь. Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения. У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе. (ru)
|
