<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>altgraph.GraphAlgo — Graph algorithms — altgraph 0.11 documentation</title>
<link rel="stylesheet" href="_static/nature.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: './',
VERSION: '0.11',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="top" title="altgraph 0.11 documentation" href="index.html" />
<link rel="next" title="altgraph.GraphStat — Functions providing various graph statistics" href="graphstat.html" />
<link rel="prev" title="altgraph.ObjectGraph — Graphs of objecs with an identifier" href="objectgraph.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="graphstat.html" title="altgraph.GraphStat — Functions providing various graph statistics"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="objectgraph.html" title="altgraph.ObjectGraph — Graphs of objecs with an identifier"
accesskey="P">previous</a> |</li>
<li><a href="index.html">altgraph 0.11 documentation</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="module-altgraph.GraphAlgo">
<span id="altgraph-graphalgo-graph-algorithms"></span><h1><a class="reference internal" href="#module-altgraph.GraphAlgo" title="altgraph.GraphAlgo: Basic graphs algoritms"><tt class="xref py py-mod docutils literal"><span class="pre">altgraph.GraphAlgo</span></tt></a> — Graph algorithms<a class="headerlink" href="#module-altgraph.GraphAlgo" title="Permalink to this headline">¶</a></h1>
<dl class="function">
<dt id="altgraph.GraphAlgo.dijkstra">
<tt class="descclassname">altgraph.GraphAlgo.</tt><tt class="descname">dijkstra</tt><big>(</big><em>graph</em>, <em>start</em><span class="optional">[</span>, <em>end</em><span class="optional">]</span><big>)</big><a class="headerlink" href="#altgraph.GraphAlgo.dijkstra" title="Permalink to this definition">¶</a></dt>
<dd><p>Dijkstra’s algorithm for shortest paths.</p>
<p>Find shortest paths from the start node to all nodes nearer
than or equal to the <em>end</em> node. The edge data is assumed to be the edge length.</p>
<div class="admonition note">
<p class="first admonition-title">Note</p>
<p class="last">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.</p>
</div>
</dd></dl>
<dl class="function">
<dt id="altgraph.GraphAlgo.shortest_path">
<tt class="descclassname">altgraph.GraphAlgo.</tt><tt class="descname">shortest_path</tt><big>(</big><em>graph</em>, <em>start</em>, <em>end</em><big>)</big><a class="headerlink" href="#altgraph.GraphAlgo.shortest_path" title="Permalink to this definition">¶</a></dt>
<dd><p>Find a single shortest path from the given start node to the given end node.
The input has the same conventions as <a class="reference internal" href="#altgraph.GraphAlgo.dijkstra" title="altgraph.GraphAlgo.dijkstra"><tt class="xref py py-func docutils literal"><span class="pre">dijkstra()</span></tt></a>. The output is a list
of the nodes in order along the shortest path.</p>
</dd></dl>
</div>
</div>
</div>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h4>Previous topic</h4>
<p class="topless"><a href="objectgraph.html"
title="previous chapter"><tt class="docutils literal"><span class="pre">altgraph.ObjectGraph</span></tt> — Graphs of objecs with an identifier</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="graphstat.html"
title="next chapter"><tt class="docutils literal"><span class="pre">altgraph.GraphStat</span></tt> — Functions providing various graph statistics</a></p>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="graphstat.html" title="altgraph.GraphStat — Functions providing various graph statistics"
>next</a> |</li>
<li class="right" >
<a href="objectgraph.html" title="altgraph.ObjectGraph — Graphs of objecs with an identifier"
>previous</a> |</li>
<li><a href="index.html">altgraph 0.11 documentation</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright 2010-2011, Ronald Oussoren, Bob Ippolito, 2004 Istvan Albert.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.2.1.
</div>
</body>
</html>