Shortest path problem (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Shortest_path_with_direct_weights.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.rand.org/pubs/papers/P923.html http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/sp-alg.ps.Z http://apps.dtic.mil/dtic/tr/fulltext/u2/661265.pdf%7Carchive-url=https:/web.archive.org/web/20151117014431/http:/www.dtic.mil/dtic/tr/fulltext/u2/661265.pdf%7Curl-status=live%7Carchive-date=November https://archive.org/details/proceedingsofthi2002acms/page/267 http://dl.acm.org/citation.cfm%3Fid=1039326%7Cjournal=Journal http://dl.acm.org/citation.cfm%3Fid=686343&CFID=563073233&CFTOKEN=28801665 http://www.eecs.umich.edu/%7Epettie/matching/Gabow-scaling-algorithms-for-network-problems.pdf https://apps.dtic.mil/sti/pdfs/ADA194031.pdf https://books.google.com/books%3Fid=oSvHzQEACAAJ https://ghostarchive.org/archive/20221009/https:/apps.dtic.mil/sti/pdfs/ADA194031.pdf |
| dbo:wikiPageID | 41985 (xsd:integer) |
| dbo:wikiPageLength | 40831 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121137261 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robotics dbr:Rubik's_Cube dbr:Bellman–Ford_algorithm dbr:Binary_heap dbr:Pathfinding dbr:Vickrey–Clarke–Groves_mechanism dbr:Computer_network dbr:Telecommunications_network dbr:Function_(mathematics) dbr:Glossary_of_graph_theory_terms dbr:Google_Maps dbr:Graph_(discrete_mathematics) dbr:Mixed_graph dbr:NP-complete dbr:Consistent_heuristic dbr:Constrained_Shortest_Path_First dbr:Contraction_hierarchies dbr:Min-plus_matrix_multiplication dbr:Very-large-scale_integration dbr:Computational_geometry dbr:Path_(graph_theory) dbr:Viterbi_algorithm dbc:Graph_distance dbr:Bucket_queue dbr:Time_complexity dbr:Topological_sorting dbr:Transportation dbr:Triangle_inequality dbr:Widest_path_problem dbr:Johnson's_algorithm dbr:Linear_programming dbr:A*_search_algorithm dbr:Algebraic_path_problem dbc:Polynomial-time_problems dbr:Dynamic_programming dbr:Flow_network dbc:Edsger_W._Dijkstra dbr:Breadth-first_search dbr:Discrete_Applied_Mathematics dbr:Discrete_optimization dbr:Floyd–Warshall_algorithm dbr:Graph_theory dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_the_ACM dbr:K_shortest_path_routing dbr:Gabow's_algorithm_(single-source_shortest_paths) dbr:Abstract_machine dbr:Bidirectional_search dbc:Computational_problems_in_graph_theory dbr:Reduced_cost dbr:Dijkstra's_algorithm dbc:Network_theory dbr:MapQuest dbr:Fibonacci_heap dbr:Hub_labels dbr:IEEE dbr:Operations_research dbr:Canadian_traveller_problem dbr:Semiring dbr:Sequence dbr:Longest_path_problem dbr:Web_mapping dbr:Six_degrees_of_separation dbr:Vertex_(graph_theory) dbr:Shortest_Path_Bridging dbr:Euclidean_shortest_path dbr:Transit_node_routing dbr:Seidel's_algorithm dbr:Stochastic_optimization dbr:Traveling_Salesman_Problem dbr:Valuation_algebra dbr:P_=_NP_problem dbr:Dipath dbr:Reptation_theory dbr:A*_search dbr:A-star_algorithm dbr:Shortest_path_tree dbr:Sparse_graph dbr:TRILL dbr:File:Shortest_path_with_direct_weights.svg |
| dbp:chapter | Single-Source Shortest Paths and All-Pairs Shortest Paths (en) |
| dbp:edition | 2 (xsd:integer) |
| dbp:pages | 580 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Introduction_to_Algorithms dbt:Authority_control dbt:Cite_book dbt:Cite_conference dbt:Cite_journal dbt:Cite_report dbt:Expand_list dbt:Expand_section dbt:Harvtxt dbt:Math dbt:More_footnotes dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Harvnb dbt:Tree_search_algorithm |
| dct:subject | dbc:Graph_distance dbc:Polynomial-time_problems dbc:Edsger_W._Dijkstra dbc:Computational_problems_in_graph_theory dbc:Network_theory |
| gold:hypernym | dbr:Problem |
| rdf:type | owl:Thing yago:WikicatComputationalProblemsInGraphTheory yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:State100024720 yago:WikicatPolynomial-timeProblems |
| 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) |
| rdfs:label | مسألة المسار الأقصر (ar) Problema del camí més curt (ca) Kürzester Pfad (de) Problema del camino más corto (es) Masalah lintasan terpendek (in) Problème de plus court chemin (fr) Cammino minimo (it) 최단 경로 문제 (ko) 最短経路問題 (ja) Problem najkrótszej ścieżki (pl) Shortest path problem (en) Задача о кратчайшем пути (ru) Problema do caminho mínimo (pt) 最短路问题 (zh) Задача про найкоротший шлях (uk) |
| owl:sameAs | freebase:Shortest path problem wikidata:Shortest path problem dbpedia-ar:Shortest path problem dbpedia-ca:Shortest path problem dbpedia-de:Shortest path problem dbpedia-es:Shortest path problem dbpedia-fa:Shortest path problem dbpedia-fr:Shortest path problem dbpedia-id:Shortest path problem dbpedia-it:Shortest path problem dbpedia-ja:Shortest path problem dbpedia-ko:Shortest path problem http://lt.dbpedia.org/resource/Trumpiausio_kelio_problema dbpedia-ms:Shortest path problem dbpedia-pl:Shortest path problem dbpedia-pt:Shortest path problem dbpedia-ru:Shortest path problem dbpedia-sr:Shortest path problem dbpedia-th:Shortest path problem dbpedia-tr:Shortest path problem dbpedia-uk:Shortest path problem http://ur.dbpedia.org/resource/کمترین_رستہ_الخوارزم dbpedia-vi:Shortest path problem dbpedia-zh:Shortest path problem https://global.dbpedia.org/id/899M http://d-nb.info/gnd/4138403-9 yago-res:Shortest path problem |
| prov:wasDerivedFrom | wikipedia-en:Shortest_path_problem?oldid=1121137261&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Shortest_path_with_direct_weights.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Shortest_path_problem |
| is dbo:wikiPageRedirects of | dbr:Applications_of_shortest_path_algorithms dbr:Shortest_path dbr:Algebraic_path_problem dbr:Apsp dbr:DAG_shortest_paths dbr:Graph_geodesic dbr:Single-pair_shortest-path_problem dbr:Shortest_Path_Problem dbr:Single-source_shortest_path_problem dbr:All-pairs_shortest_path_problem dbr:The_Shortest_Paths dbr:Single-destination_shortest-path_problem dbr:Single-destination_shortest_path_problem dbr:Single-destination_shortestpath_problem dbr:Single-source_shortest-path_problem dbr:Single-source_shortest-paths_algorithm...ected_graphs_with_nonnegative_weights dbr:Single-source_shortestpath_problem dbr:Single_destination_shortest-path_problem dbr:Single_destination_shortest_path_problem dbr:Single_destination_shortestpath_problem dbr:Single_source_shortest-path_problem dbr:Single_source_shortest_path_problem dbr:Single_source_shortestpath_problem dbr:Singledestination_shortest-path_problem dbr:Singledestination_shortest_path_problem dbr:Singledestination_shortestpath_problem dbr:Singlesource_shortest-path_problem dbr:Singlesource_shortest_path_problem dbr:Singlesource_shortestpath_problem dbr:Shortest-distance_problems dbr:Shortest-path dbr:Shortest-path_algorithms dbr:Shortest-path_problem dbr:Shortest-path_problems dbr:Shortest-path_routing dbr:Shortest-paths dbr:Shortest_Path_Algorithms dbr:Shortest_path_algorithm dbr:Shortest_path_algorithms dbr:Shortest_path_problems dbr:Shortest_path_routing dbr:Shortest_paths dbr:Shortestpath dbr:Shortestpath_problem dbr:Shortestpath_problems dbr:Shortestpaths dbr:APSP dbr:All-pairs_shortest_path dbr:All_pairs_shortest_path dbr:All_pairs_shortest_path_problem dbr:Negative_cycle |
| is dbo:wikiPageWikiLink of | dbr:Prim's_algorithm dbr:Quantum_complexity_theory dbr:Science_Fell_in_Love,_So_I_Tried_to_Prove_It dbr:List_of_algorithms dbr:Melissa_Chase dbr:Minimum_distance dbr:Online_optimization dbr:Reactive_planning dbr:Price's_model dbr:Declarative_programming dbr:Algorithmic_technique dbr:Any-angle_path_planning dbr:Betweenness_centrality dbr:List_of_Dutch_inventions_and_innovations dbr:List_of_graph_theory_topics dbr:Pathfinding dbr:Incidence_and_Symmetry_in_Design_and_Architecture dbr:Indifference_graph dbr:Ingo_Althöfer dbr:Introduction_to_Tropical_Geometry dbr:Navigation dbr:Vickrey–Clarke–Groves_mechanism dbr:Maximum_subarray_problem dbr:Gateway-to-Gateway_Protocol dbr:Network_theory dbr:Online_algorithm dbr:Eikonal_equation dbr:Geodesic dbr:Glossary_of_artificial_intelligence dbr:Graph_(discrete_mathematics) dbr:Consistent_heuristic dbr:Contraction_hierarchies dbr:Convex_Polytopes dbr:Theta* dbr:Dan_Willard dbr:Min-plus_matrix_multiplication dbr:Optical_mesh_network dbr:Optimal_substructure dbr:Andrew_V._Goldberg dbr:Ant_colony_optimization_algorithms dbr:Applications_of_shortest_path_algorithms dbr:Shortest_path dbr:Steiner_tree_problem dbr:Closeness_centrality dbr:Computer_program dbr:Zopfli dbr:Fully_polynomial-time_approximation_scheme dbr:Path_(graph_theory) dbr:Spsp dbr:Map_database_management dbr:Broadcast_(parallel_pattern) dbr:Topological_sorting dbr:UCPH_Department_of_Computer_Science dbr:UNITY_(programming_language) dbr:GNRS_conjecture dbr:Link-state_routing_protocol dbr:Minimum-cost_flow_problem dbr:Temporally_ordered_routing_algorithm dbr:Algebraic_path_problem dbr:Dynamic_programming dbr:Edsger_W._Dijkstra dbr:Euclidean_minimum_spanning_tree dbr:Flow_network dbr:Parallel_all-pairs_shortest_path_algorithm dbr:Centrality dbr:Farthest-first_traversal dbr:Floyd–Warshall_algorithm dbr:Graph_edit_distance dbr:Graph_neural_network dbr:Graph_theory dbr:Iterative_deepening_A* dbr:Journey_planner dbr:Quasiregular_element dbr:Auction_algorithm dbr:J._Hyam_Rubinstein dbr:Jeffrey_Uhlmann dbr:Monotone_priority_queue dbr:Biological_network_inference dbr:Efficiency_(network_science) dbr:Hexagonal_Efficient_Coordinate_System dbr:Differential_calculus dbr:Dijkstra's_algorithm dbr:Distance_(graph_theory) dbr:Automotive_navigation_system dbr:Autonomous_mobility_on_demand dbr:Circulation_problem dbr:Fine-grained_reduction dbr:Greedy_algorithm dbr:Apsp dbr:DAG_shortest_paths dbr:Graph_geodesic dbr:Kleene_algebra dbr:Network_science dbr:Open_Shortest_Path_First dbr:Canadian_traveller_problem dbr:Capacitated_arc_routing_problem dbr:Search_algorithm dbr:Christofides_algorithm dbr:Longest_path_problem dbr:Robotic_mapping dbr:Routing dbr:SSSP dbr:Shortest-path_tree dbr:Strongly_regular_graph dbr:Single-pair_shortest-path_problem dbr:Six_Degrees_of_Kevin_Bacon dbr:Turn-by-turn_navigation dbr:Euclidean_shortest_path dbr:List_of_unsolved_problems_in_computer_science dbr:The_Art_of_Computer_Programming dbr:Rotation_distance dbr:Route_assignment dbr:Transit_node_routing dbr:Finite-state_machine dbr:Navigational_Algorithms dbr:Motion_planning dbr:Multi-agent_pathfinding dbr:Path_protection dbr:Seidel's_algorithm dbr:Solver dbr:Parallel_single-source_shortest_path_algorithm dbr:Physarum_polycephalum dbr:Small-world_experiment dbr:Random_walk_closeness_centrality dbr:United_States_of_America_Computing_Olympiad dbr:X_+_Y_sorting dbr:Turn_restriction_routing dbr:Stretch_factor dbr:Shortest_Path_Problem dbr:Single-source_shortest_path_problem dbr:All-pairs_shortest_path_problem dbr:The_Shortest_Paths dbr:Single-destination_shortest-path_problem dbr:Single-destination_shortest_path_problem dbr:Single-destination_shortestpath_problem dbr:Single-source_shortest-path_problem dbr:Single-source_shortest-paths_algorithm...ected_graphs_with_nonnegative_weights dbr:Single-source_shortestpath_problem dbr:Single_destination_shortest-path_problem dbr:Single_destination_shortest_path_problem dbr:Single_destination_shortestpath_problem dbr:Single_source_shortest-path_problem dbr:Single_source_shortest_path_problem dbr:Single_source_shortestpath_problem dbr:Singledestination_shortest-path_problem dbr:Singledestination_shortest_path_problem dbr:Singledestination_shortestpath_problem dbr:Singlesource_shortest-path_problem dbr:Singlesource_shortest_path_problem dbr:Singlesource_shortestpath_problem dbr:Shortest-distance_problems dbr:Shortest-path dbr:Shortest-path_algorithms dbr:Shortest-path_problem dbr:Shortest-path_problems dbr:Shortest-path_routing dbr:Shortest-paths dbr:Shortest_Path_Algorithms dbr:Shortest_path_algorithm dbr:Shortest_path_algorithms dbr:Shortest_path_problems dbr:Shortest_path_routing dbr:Shortest_paths dbr:Shortestpath dbr:Shortestpath_problem dbr:Shortestpath_problems dbr:Shortestpaths dbr:APSP dbr:All-pairs_shortest_path dbr:All_pairs_shortest_path dbr:All_pairs_shortest_path_problem dbr:Negative_cycle |
| is foaf:primaryTopic of | wikipedia-en:Shortest_path_problem |
