Rename DigraphDijkstra

[mtorpey]

DigraphShortestPath and DigraphDijkstra are two closely related functions that both find the shortest path between two vertices, where "shortest" means "fewest edges".

The algorithm they're using appears to be basically the same: it's a breadth-first search starting at the source vertex and proceeding until the destination vertex is found. Dijkstra's algorithm in general is smarter than this, since it uses edge lengths to decide where to explore next; but we don't have edge lengths, so this isn't relevant here.

The reason both operations are valuable is that they have different outputs. They both return two lists, but don't be fooled! DigraphShortestPath returns

a pair of lists [v,a] as follows:
• v is the list [v_1, v_2, ..., v_n].
• a is the list of positive integers [a_1, a_2, ..., a_n-1] where for each each i < n, a_i is the position of v_i+1 in OutNeighboursOfVertex(digraph,v_i) corresponding to the edge e_i.

whereas DigraphDijkstra returns

two lists. Each element of the first list is the distance of the corresponding element from source. If a vertex was not visited in the process of calculating the shortest distance to target or if there is no path connecting that vertex with source, then the corresponding distance is infinity. Each element of the second list gives the previous vertex in the shortest path from source to the corresponding vertex. For source and for any vertices that remained unvisited this will be -1.

The issue here is that "DigraphDijkstra" isn't a helpful name. We usually name our operations after the thing they return rather than the author of the core algorithm we're using. The output of DigraphShortestPath is consistent with other "paths" in the package, so this is reasonable. Hence we need a name to replace "Dijkstra".

The main thing that distinguishes Dijkstra from ShortestPath is that it gives information on how to reach multiple vertices in the shortest distance: all vertices in the connected component, or else all the ones it can find while searching for destination. Hence, a good option might be DigraphShortestPaths, which I don't think would be too confusing.

We could make this change easily, although we should make sure to preserve DigraphDijkstra as a synonym for backwards compatibility, till 2.0

Any thoughts?

[mtorpey]

Added to the VIP board as an easy task, noting that it's important we keep DigraphDijkstra as a synonym to preserve backwards compatibility.

[mtorpey]

@devansh2605 will do this!