| 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)