Skip to content
This repository has been archived by the owner on Oct 8, 2021. It is now read-only.

add widest (/maximum capacity) path algorithm #1557

Open
zurKreuzigungLinks opened this issue Apr 8, 2021 · 2 comments
Open

add widest (/maximum capacity) path algorithm #1557

zurKreuzigungLinks opened this issue Apr 8, 2021 · 2 comments

Comments

@zurKreuzigungLinks
Copy link

"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
Copy link

saolof commented Apr 13, 2021

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
Copy link
Owner

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

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants