.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "tutorials/shortest_path_visualisation.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_tutorials_shortest_path_visualisation.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_tutorials_shortest_path_visualisation.py:


.. _tutorials-shortest-paths:

==============
Shortest Paths
==============

This example demonstrates how to find the shortest distance between two vertices
of a weighted or an unweighted graph.

.. GENERATED FROM PYTHON SOURCE LINES 11-14

.. code-block:: Python

    import igraph as ig
    import matplotlib.pyplot as plt








.. GENERATED FROM PYTHON SOURCE LINES 15-16

To find the shortest path or distance between two nodes, we can use :meth:`igraph.GraphBase.get_shortest_paths`. If we're only interested in counting the unweighted distance, then we can do the following:

.. GENERATED FROM PYTHON SOURCE LINES 16-24

.. code-block:: Python

    g = ig.Graph(
        6,
        [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
    )
    results = g.get_shortest_paths(1, to=4, output="vpath")

    # results = [[1, 0, 2, 4]]








.. GENERATED FROM PYTHON SOURCE LINES 25-26

We can print the result of the computation:

.. GENERATED FROM PYTHON SOURCE LINES 26-32

.. code-block:: Python

    if len(results[0]) > 0:
        # The distance is the number of vertices in the shortest path minus one.
        print("Shortest distance is: ", len(results[0])-1)
    else:
        print("End node could not be reached!")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Shortest distance is:  3




.. GENERATED FROM PYTHON SOURCE LINES 33-35

If the edges have weights, things are a little different. First, let's add
weights to our graph edges:

.. GENERATED FROM PYTHON SOURCE LINES 35-37

.. code-block:: Python

    g.es["weight"] = [2, 1, 5, 4, 7, 3, 2]








.. GENERATED FROM PYTHON SOURCE LINES 38-42

To get the shortest paths on a weighted graph, we pass the weights as an
argument. For a change, we choose the output format as ``"epath"`` to
receive the path as an edge list, which can be used to calculate the length
of the path.

.. GENERATED FROM PYTHON SOURCE LINES 42-55

.. code-block:: Python

    results = g.get_shortest_paths(0, to=5, weights=g.es["weight"], output="epath")

    # results = [[1, 3, 5]]

    if len(results[0]) > 0:
        # Add up the weights across all edges on the shortest path
        distance = 0
        for e in results[0]:
            distance += g.es[e]["weight"]
        print("Shortest weighted distance is: ", distance)
    else:
        print("End node could not be reached!")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Shortest weighted distance is:  8




.. GENERATED FROM PYTHON SOURCE LINES 56-60

.. note::

    - :meth:`igraph.GraphBase.get_shortest_paths` returns a list of lists becuase the `to` argument can also accept a list of vertex IDs. In that case, the shortest path to all each vertex is found and stored in the results array.
    - If you're interested in finding *all* shortest paths, take a look at :meth:`igraph.GraphBase.get_all_shortest_paths`.

.. GENERATED FROM PYTHON SOURCE LINES 62-63

In case you are wondering how the visualization figure was done, here's the code:

.. GENERATED FROM PYTHON SOURCE LINES 63-80

.. code-block:: Python

    g.es['width'] = 0.5
    g.es[results[0]]['width'] = 2.5

    fig, ax = plt.subplots()
    ig.plot(
        g,
        target=ax,
        layout='circle',
        vertex_color='steelblue',
        vertex_label=range(g.vcount()),
        edge_width=g.es['width'],
        edge_label=g.es["weight"],
        edge_color='#666',
        edge_align_label=True,
        edge_background='white'
    )
    plt.show()



.. image-sg:: /tutorials/images/sphx_glr_shortest_path_visualisation_001.png
   :alt: shortest path visualisation
   :srcset: /tutorials/images/sphx_glr_shortest_path_visualisation_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.142 seconds)


.. _sphx_glr_download_tutorials_shortest_path_visualisation.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: shortest_path_visualisation.ipynb <shortest_path_visualisation.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: shortest_path_visualisation.py <shortest_path_visualisation.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: shortest_path_visualisation.zip <shortest_path_visualisation.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_