.. _sphx_glr_api_gallery_graph_theory_shortest_paths:

Shortest paths
----------------

Dijkstra, Bellman-Ford, and Floyd-Warshall.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Runs Dijkstra&#x27;s algorithm from one source on a small weighted graph and draws the resulting shortest-path tree. Bellman-Ford gives the same distances there, and takes over on a graph with a negative edge, where Dijkstra&#x27;s greedy assumption breaks down.">

.. only:: html

  .. image:: /api/gallery/graph_theory/shortest_paths/images/thumb/sphx_glr_plot_01_dijkstra_vs_bellman_ford_thumb.png
    :alt:

  :doc:`/api/gallery/graph_theory/shortest_paths/plot_01_dijkstra_vs_bellman_ford`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Dijkstra's shortest-path algorithm (and when Bellman-Ford is needed)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Computes every shortest-path distance in a weighted graph at once with the Floyd-Warshall algorithm, and checks that it agrees with running Dijkstra&#x27;s algorithm from every vertex.">

.. only:: html

  .. image:: /api/gallery/graph_theory/shortest_paths/images/thumb/sphx_glr_plot_02_floyd_warshall_thumb.png
    :alt:

  :doc:`/api/gallery/graph_theory/shortest_paths/plot_02_floyd_warshall`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Floyd-Warshall: all-pairs shortest paths</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/graph_theory/shortest_paths/plot_01_dijkstra_vs_bellman_ford
   /api/gallery/graph_theory/shortest_paths/plot_02_floyd_warshall