שאלה של נוגה אלון שנתקלתי בקובץ של שלומי:

נתון גרף לא מכוון עם משקלות שלמים בין 1 ל |V| וזוג צמתצריך למצוא מסלול בין s ל t כך שהמשקל המירבי של קשת במסלול הינו מינימלי.

פתרתי עם דייקסטרה כשאני משנה את מתודת הרילאקס כך שהיא משתמשת במקסימום במקום בחיבור.

הסיבוכית היא כמו דייקסטרה אבל ראיתי פתרון של שלומי בסיבוכיות לינארית.

האם גם סיבוכיות כמו של דייקסטרה זה מספיק?

Hi,

The problem with your solution is that you don't seem to use the given assumption regarding the weight of edges.

I don't know Shlomi's solution, here is another one in O(|E|*a(|V|)) (which is so close to linear I doubt the grade would be reduced):

Sort the edges in O(|E|) (for example by bucket-sort with buckets for 1,…,|V|).

Use the Union-Find d.s. and as in Kruskal's algorithm join the sets of u,v as you get to the edge (u,v) in the sorted list of edges.

When find(s)==find(v) for the first time, return the weight of the latest edge.

Or.

i didn't understand your solution…

notice that you asked to return the path, not the weight of the maximal edge…

Hi,

If you understand why is this the weight of the maximal edge there is no problem to also return the path.

(Just run a BFS from s on the graph with only edges with weight lower or equal to the weight of the maximal edge)

The reason this is the weight of the maximal edge is:

The maximal weight on a specific path p from s to t is W <=> The path p appears on G_W but not on G_(W-Eps) for any Eps>0.

(Where G_W is the graph with only edges with weights <= W)

More intuitively, we are starting with a graph without any edges and starting to add the edges to the graph (starting with the lowest

weight in an increasing manner) - the first time there will be any path from s to t we can be sure that this is the path from s to t with

the lowest maximal weight (as it is a path, and if there was a path where all the weights are lower we would find it earlier).

Or.

Hi,

In this case a linear solution would give you full points, a solution like Or's would probably get you about 8-9 points, and a solution using Dijkstra would probably get you 4-5 points. In practice there might not be a big difference between $O(\alpha(n))$ and linear, but in theory (and this course is theoretical), there is, and you would definitely lose points for it!

The idea is to use BFS, but only add edges which weigh up to 1, then 2 and so on. So if you're at the stage in BFS when you are adding edges of weight up to 6, and you see edges of weight 3, 4, 5 - you add them all, and continue adding until you can no longer add edges. The implementation is a bit tricky - it's similar in some sense to the implementation we did in the tirgul for Dijkstra with weights 0,1,2, and I would suggest to make sure you can continue solving the question from here.

Shai

is it possible to use Dijkstra with |V| size array and pointer instead of Fibonacci heap and then extract min will take O(1) (i.e O(V) for the algorithm)?