| rdfs:comment
| - 在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。 (zh)
- En teoria de grafs i ciència computacional teòrica, el problema del camí més llarg és el problema de trobar un camí simple de màxima longitud possible en un determinat graf. Un camí s'anomena simple si no té cap vèrtex repetit; la longitud d'un camí es pot mesurar pel seu nombre d'arestes, o (en grafs ponderats) per la suma dels pesos de les seves arestes. (ca)
- En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP.
* Datos: Q2916352 (es)
- Die Aufgabe, den einfachen Weg maximaler Länge in einem gegebenen Graphen zu finden, bezeichnet man in der Graphentheorie und der theoretischen Informatik als longest path problem (englisch für Problem des längsten Weges). Ein Weg heißt einfach, wenn er keinen Knoten mehrfach enthält. Die Länge des Weges kann auf zwei Arten gemessen werden: entweder durch die Anzahl der Kanten oder (in einem gewichteten Graphen) durch die Summe der Gewichte seiner Kanten. (de)
- In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is d (en)
- En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin. (fr)
- Em teoria dos grafos e ciência da computação teórica, o problema do caminho mais longo é encontrar um caminho simples de comprimento máximo num dado grafo. Um caminho é chamado simples se não tem nenhum vértice repetido; O comprimento de um caminho pode ser medido tanto pelo seu número de arestas, ou (em grafos ponderados) pela soma dos pesos das suas bordas. Em contraste com o problema do caminho mais curto, que pode ser resolvido em tempo polinomial em gráficos sem ciclos de peso negativo, o problema do caminho mais longo é NP-difícil, o que significa que ele não pode ser resolvido em tempo polinomial para grafos arbitrários a menos que P = NP. Fortes resultados difíceis são também conhecidos por mostrar que é difícil aproximar. No entanto, ele tem uma solução em tempo linear para grafos (pt)
- Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пут (ru)
|
![[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)
![[RDF Data]](/fct/images/sw-rdf-blue.png)