All pairs shortest path

All pairs shortest path

Finding all pairs shortest path consists of finding the shortest distance between every pair of nodes in a possibly directed graph. Various means of doing so are known, and the following list gives a few of the common methods:
*Floyd-Warshall algorithm is an elegant, quickly implementable O(n^3) algorithm (Assumes absence of negatively-weighed cycles).
*Johnson's algorithm is harder to implement, but might perform better for sparse graphs.
*Algorithms for single source problem might also be repeatedly used, although they often perform worse or are harder to optimize.

ee also

*Shortest path problem
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Shortest path problem — A graph with 6 vertices and 7 edges 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. An example is… …   Wikipedia

  • Shortest-Path — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Shortest Path — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… …   Wikipedia

  • Kürzester Pfad — Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei Knoten, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den wenigsten Knoten. Sollten… …   Deutsch Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • UNITY (programming language) — The UNITY programming language was constructed by K. Mani Chandy and Jayadev Misra for their book Parallel Program Design: A Foundation . It is a rather theoretical language, which tries to focus on what , instead of where , when or how . The… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”