edgegraph.pathfinding.shortestpath.single_pair_shortest_path

edgegraph.pathfinding.shortestpath.single_pair_shortest_path(uni, start, dest, *, weightfunc=None, direction_sensitive=0, unknown_handling=2, ff_via=None, method='dijkstra')

Find the shortest path between two vertices in the given universe.

This function is a frontend for various implementations / algorithms for computing the single-pair shortest path (SPSP) problem; that is, finding the shortest path between a single pair of nodes. It returns the path between the given nodes (also sometimes called the route), as well as the total weight (also sometimes called cost).

Parameters:

• uni (Universe) – Universe to search within. Set to None for no universe limiting.

• start (Vertex) – Vertex to start searching from.

• dest (Vertex) – Vertex to search for.

• weightfunc (Callable | None) –

  Callback function to determine the weight (also sometimes called cost) of transiting between two vertices. If not specified, the default behavior is to weight all edges equally (weight of 1).

  edgegraph.pathfinding.shortestpath.weightfunc(v1, v2)

  Custom weights on edges are possible via the weightfunc argument. It must be a callable object accepting exactly two position arguments, u and v, which represent a “from” and “to” vertex. It must return a number representing the weight of pathing from u to v.

  See also

  Hint: find_links() can quickly find you the edges(s) between these two!

  Warning

  Some method options require that all edges are weighted positively, or that no negative-weight cycles exist.

  Parameters:

  • v1 – The “from” vertex

  • v2 – The “to” vertex

  Returns:

  Cost of transiting from v1 to v2

• method (str) –

  The backend algorithm to use. Options are:

  • "dijkstra": Use Dijkstra’s algorithm with a priority queue; worst case is \(O(V^2)\). No negative weights are allowed. (default)

  See also

  More information on these options is available in the Pathfinding section.

• direction_sensitive (int) –

  Directly passed through to neighbors(). This may be one of:

  • DIR_SENS_FORWARD (default), to follow edges only forward (when directed),

  • DIR_SENS_ANY, to follow edges regardless of their direction,

  • DIR_SENS_BACKWARD, to only follow edges backwards (when directed).

• unknown_handling (int) –

  Directly passed through to neighbors(). This may be one of:

  • LNK_UNKNOWN_ERROR (default), to throw an exception,

  • LNK_UNKNOWN_NEIGHBOR, to treat such edges as neighbors (and take the edge),

  • LNK_UNKNOWN_NONNEIGHBOR, to treat such edges as non-neighbors (do not take the edge).

• ff_via (Callable | None) –

  Directly passed through to neighbors() function’s filterfunc argument.

  edgegraph.pathfinding.shortestpath.ff_via(e, v2)

  Determines if an edge (e) from a given vertex to another (v2) should be followed. If not, that entire section of the graph will not be searched (assuming no other entries to that area).

  Parameters:

  • e – The edge connecting v1 to v2.

  • v2 – The vertex under consideration.

  Returns:

  Whether or not v2 should be considered a neighbor of v, when reached via e.

Returns:

A two-tuple of:

1. A list of Vertex objects representing the actual path taken to reach from start to dest. The start and end vertices are included in this list.

   If there is no path between the given vertices, None is given here instead. If the start and destination vertices are the same, the value here will be [v1, v1].

2. The total weight of the path between start and end vertices (the sum of the given weightfunc’s return for all hops in the discovered path).

   If there is no path between the given vertices, None is given here instead. If the start and destination vertices are the same, the value here will be zero regardless of edge weighting (as there is no distance between an object and itself).

Return type:

tuple[list[Vertex] | None, float | None]