I found an interesting problem in the archive of Iran National OI problems. The problem statement in English is:
Let D be a weighted directed graph. The length of a path P is defined as the minimum weight of the edges along P. The distance between vertices u and v is the maximum length among all paths from u to v. Your task is to find the distance between every pair of vertices in O(n·e + n²) time.
I have a O(n(e + n) lg n) solution for this using Dijkstra, but I haven't been able to solve it in O(n·e + n²), so I'm looking for a solution. Any help would be appreciated!
I wonder if there is something like DSU, but for maintaining Strongly Connected Components (and the DAG between them) in some reasonable amortized time complexity. It would also need to support the following slightly stronger requirement
If something like that exists, then you could add edges to your graph, one by one, in decreasing order of bandwidth. If $$$v$$$ is reachable from $$$u$$$ for the first time when adding an edge of weight $$$w$$$, then $$$d(u, v) = w$$$.
Working backwards from the time complexity — if the "report newly connected pairs" phase of the algorithm works in $$$O($$$ number of pairs reported $$$)$$$, then that amortizes to $$$O(n^2)$$$ which is part of the expected solution. So, what we would need is for the maintenance of our data structure to take $$$O(en)$$$ time overall (excluding the pairs reporting, which we already account for).
Maybe someone who remembers Kosaraju or Tarjan better than me can say if an "edge by edge" version of them, in the style of DSU, could work in $$$O(n)$$$ time per edge (amortized).
I think for making the graph complete , we can add edge u->v with weight 0 if there no edge between them and the answers are same as before. but how can we report newly connected pairs
Compute the strongly connected components of the graph. For a path between two nodes that are in the same component, the distance between these two nodes is the same as the edge with maximum weight inside that component. For all the other pairs, compress the SCC's into single nodes. The transformed graph is acyclic, so you can compute a topological sort of that graph. For each compressed node, compute the distance to each other compressed node using DP. Calculating that distance requires $$$O(N+E)$$$ time for each compressed node, so the total time-complexity turns out to be just $$$O(N*(N+E))$$$.
I think "For a path between two nodes that are in the same component, the distance between these two nodes is the same as the edge with maximum weight inside that component" is not correct. for example consider a cycle where 1->2->3->4->1 and weight of edge 1->2 be 5 and all others 1 so distance of each pair expect 1->2 is 1 which is not weight of edge with maximum weight inside that component.
There has been a misunderstanding in your task description then. If we consider a path going from node $$$u$$$ to node $$$v$$$, are we allowed to visit $$$u$$$ multiple times? And are we allowed to visit $$$v$$$ multiple times?
I think the answers can not improve by going throw the same vertex multiple times
as by removing some edges the minimum doesn't decrease, so we can make the path shorter if it visits a vertex multiple times by removing the cycles for example if a path goes like v1 -> v2 -> ... -> vk -> u -> w1 -> w2 -> ... -> u -> v(k+1) -> ... -> v(n) we can cut the path like v1 -> v2 -> ... -> vk -> u -> v(k+1) -> ... -> v(n) and the "length" ( minimum weight ) of the path didn't decrease
So it doesn't matter.