summaryrefslogtreecommitdiffstats
path: root/python/altgraph/doc/graphalgo.rst
diff options
context:
space:
mode:
Diffstat (limited to 'python/altgraph/doc/graphalgo.rst')
-rw-r--r--python/altgraph/doc/graphalgo.rst26
1 files changed, 26 insertions, 0 deletions
diff --git a/python/altgraph/doc/graphalgo.rst b/python/altgraph/doc/graphalgo.rst
new file mode 100644
index 000000000..84d492f44
--- /dev/null
+++ b/python/altgraph/doc/graphalgo.rst
@@ -0,0 +1,26 @@
+:mod:`altgraph.GraphAlgo` --- Graph algorithms
+==================================================
+
+.. module:: altgraph.GraphAlgo
+ :synopsis: Basic graphs algoritms
+
+.. function:: dijkstra(graph, start[, end])
+
+ Dijkstra's algorithm for shortest paths.
+
+ Find shortest paths from the start node to all nodes nearer
+ than or equal to the *end* node. The edge data is assumed to be the edge length.
+
+ .. note::
+
+ Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
+ This code does not verify this property for all edges (only the edges examined until the end
+ vertex is reached), but will correctly compute shortest paths even for some graphs with negative
+ edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
+
+
+.. function:: shortest_path(graph, start, end)
+
+ Find a single shortest path from the given start node to the given end node.
+ The input has the same conventions as :func:`dijkstra`. The output is a list
+ of the nodes in order along the shortest path.