add widest (/maximum capacity) path algorithm
zurKreuzigungLinks opened this issue · 2 comments
"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:
- Use existing shortest path algorithm
- Change edge weights w to 1/w:
distmx::AbstractMatrix{T}=1 ./ weights(g) - Use the max edge weight as new distance:
tentative_g_score = max(g_score[current] + distmx[current, neighbor]) - Change Priority to the current "distance":
priority = tentative_g_score
That should be it if I didn't forget anything.
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
This might be better in LightGraphsFlows.jl where they are concerned with capacity algorithms.