Vous êtes un professionnel et vous avez besoin d'une formation ? Programmation Python
Les fondamentaux Voir le programme détaillé

Module « scipy.sparse.csgraph »

Fonction yen - module scipy.sparse.csgraph

Signature de la fonction yen

def yen(csgraph, source, sink, K, *, directed=True, return_predecessors=False, unweighted=False) 

Description

help(scipy.sparse.csgraph.yen)

    yen(csgraph, source, sink, K, *, directed=True, return_predecessors=False,
        unweighted=False)

    Yen's K-Shortest Paths algorithm on a directed or undirected graph.

    .. versionadded:: 1.14.0

    Parameters
    ----------
    csgraph : array_like, or sparse array or matrix, 2 dimensions
        The N x N array of distances representing the input graph.
    source : int
        The index of the starting node for the paths.
    sink : int
        The index of the ending node for the paths.
    K : int
        The number of shortest paths to find.
    directed : bool, optional
        If ``True`` (default), then find the shortest path on a directed graph:
        only move from point ``i`` to point ``j`` along paths ``csgraph[i, j]``.
        If False, then find the shortest path on an undirected graph: the
        algorithm can progress from point i to j along ``csgraph[i, j]`` or
        ``csgraph[j, i]``.
    return_predecessors : bool, optional
        If ``True``, return the size ``(M, N)`` predecessor matrix. Default: ``False``.
    unweighted : bool, optional
        If ``True``, then find unweighted distances. That is, rather than finding
        the path between each point such that the sum of weights is minimized,
        find the path such that the number of edges is minimized. Default: ``False``.

    Returns
    -------
    dist_array : ndarray
        Array of size ``M`` of shortest distances between the source and sink nodes.
        ``dist_array[i]`` gives the i-th shortest distance from the source to the sink
        along the graph. ``M`` is the number of shortest paths found, which is less than or
        equal to `K`.
    predecessors : ndarray
        Returned only if ``return_predecessors == True``.
        The M x N matrix of predecessors, which can be used to reconstruct
        the shortest paths.
        ``M`` is the number of shortest paths found, which is less than or equal to `K`.
        Row ``i`` of the predecessor matrix contains
        information on the ``i``-th shortest path from the source to the sink: each
        entry ``predecessors[i, j]`` gives the index of the previous node in the
        path from the source to node ``j``.  If the path does not pass via node ``j``,
        then ``predecessors[i, j] = -9999``.

    Raises
    ------
    NegativeCycleError:
        If there are negative cycles in the graph

    Notes
    -----
    Yen's algorithm is a graph search algorithm that finds single-source `K`-shortest
    loopless paths for a graph with nonnegative edge cost. The algorithm was published
    by Jin Y. Yen in 1971 and employs any shortest path algorithm to find the best path,
    then proceeds to find ``K - 1`` deviations of the best path.

    The algorithm is based on Dijsktra's algorithm for finding each shortest path.
    In case there are negative edges in the graph, Johnson's algorithm is applied.

    If multiple valid solutions are possible, output may vary with SciPy and
    Python version.

    References
    ----------
    .. [1] https://en.wikipedia.org/wiki/Yen%27s_algorithm
    .. [2] https://www.ams.org/journals/qam/1970-27-04/S0033-569X-1970-0253822-7/

    Examples
    --------
    >>> from scipy.sparse import csr_array
    >>> from scipy.sparse.csgraph import yen

    >>> graph = [
    ... [0, 1, 2, 0],
    ... [0, 0, 0, 1],
    ... [2, 0, 0, 3],
    ... [0, 0, 0, 0]
    ... ]
    >>> graph = csr_array(graph)
    >>> print(graph)
    <Compressed Sparse Row sparse array of dtype 'int64'
    	with 5 stored elements and shape (4, 4)>
    	Coords	Values
    	(0, 1)	1
    	(0, 2)	2
    	(1, 3)	1
    	(2, 0)	2
    	(2, 3)	3

    >>> dist_array, predecessors = yen(csgraph=graph, source=0, sink=3, K=2,
    ...                                directed=False, return_predecessors=True)
    >>> dist_array
    array([2., 5.])
    >>> predecessors
    array([[-9999,     0, -9999,     1],
        [-9999, -9999,     0,     2]], dtype=int32)

    

Vous êtes un professionnel et vous avez besoin d'une formation ? Programmation Python
Les fondamentaux Voir le programme détaillé