add widest (/maximum capacity) path algorithm

[zurKreuzigungLinks]

"In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem." https://en.wikipedia.org/wiki/Widest_path_problem

I needed this and implemented it as it is quite simple. I just duplicated your functions and changed them a bit like so:

1. Use existing shortest path algorithm
2. Change edge weights w to 1/w: distmx::AbstractMatrix{T}=1 ./ weights(g)
3. Use the max edge weight as new distance:tentative_g_score = max(g_score[current] + distmx[current, neighbor])
4. Change Priority to the current "distance":priority = tentative_g_score

That should be it if I didn't forget anything.

[saolof]

Right, the widest path problem is fairly straightforwardly reduced to the shortest/longest (non-cyclic) path problem. You replace addition with min/max basically.

If you have the adjacency matrix A, then they have a fairly beautiful relationship to each other in the following way using matrix multiplication over a semiring:

• entries of the matrix A^n will count paths of length n between i and j
• entries of min_tropical.(A)^n (so min as addition and normal addition as multiplication) will give the shortest path of length n between i and j.
• entries of min_max_lattice.(A)^n will give the widest path of length n between i and j

... and similarly, Floyd Warshall can count noncyclic paths, find the shortest noncyclic path, or to find widest paths, by doing the same straightforward replacement

[sbromberger]

This might be better in LightGraphsFlows.jl where they are concerned with capacity algorithms.