'How to modify dijkstra to calculate minimum maximum bottleneck route?

This is the dijkstra I have right now coded with Python, but I don't know how I should modify this to calculate the route with the smallest possible max weight.

def dijkstra(g,s):
    
    for i in g.vertices:
        g.dist[i] = INF
        g.pred[i] = 0
        
    g.dist[s] = 0
    
    queue = [i for i in g.vertices]
    
    while len(queue) > 0:
        minval = INF
        u = 0
        for vert in queue:
            if g.dist[vert] < minval:
                minval = g.dist[vert]
                u = vert
        queue.remove(u)         
        
        for edge in g.adj_list[u]:
            v = edge.node
            if g.dist[v] > g.dist[u] + edge.weight:
                g.dist[v] = g.dist[u] + edge.weight
                g.pred[v] = u
pythonalgorithmdijkstraweighted-graph


Solution 1:[1]

if i don't mistake you ,try it,S is 1,T is 5

5 5
1 2 12
1 3 11
2 4 9
3 4 11
4 5 11

Solution 2:[2]

This is the working algorithm to find the min max bottleneck route:

def dijkstra(g,s):
    
    for i in g.vertices:
        g.dist[i] = INF
        g.pred[i] = 0
        
    g.dist[s] = 0
    
    queue = [i for i in g.vertices]
    
    while len(queue) > 0:
        minval = INF
        u = 0
        for vert in queue:
            if g.dist[vert] < minval:
                minval = g.dist[vert]
                u = vert
        queue.remove(u)         
        
        for edge in g.adj_list[u]:
            v = edge.node
            if g.dist[v] > max(g.dist[u], edge.weight):
                g.dist[v] = max(g.dist[u], edge.weight)
                g.pred[v] = u

as per OP @niaragua's edit to the question.

Solution 3:[3]

I cannot make sure maximum bottleneck route?I guess it is a path from S to T and the minimum edge on it is maximum. If this, I do not think we can set a queue keeping the montonicity (I feel it is the nature of diji). Maybe you can only use Binary Search with bfs?

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 a1b3c7d9
Solution 2 vinzee
Solution 3 vinzee

Related Questions