Shortest Path Problem

The shortest path problem seeks to find the shortest path (a.k.a. graph geodesic) connecting two specific vertices  of a directed or undirected graph. The length of the graph geodesic between these points  is called the graph distance between  and . Common algorithms for solving the shortest path problem include the Bellman-Ford algorithm and Dijkstra's algorithm.

The Wolfram Language function FindShortestPath[g, u, v] can be used to find one (of possibly mutiple) shortest path between vertices  and  in a graph .

The so-called reaching algorithm can solve the shortest path problem on an -edge graph in  steps for an acyclic digraph although it allows edges to be traversed opposite their direction and given a negative length.

---

REFERENCES

Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 224-227, 1990.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength