

Shortest Path with Limited Hops

Question

Let an undirected simple graph $G(V, E)$ be given with $n$ nodes and $m$ edges. The edges have an associated positive weight: $w(x,y) > 0$ for the edge between node $x$ and $y$. This questions concerns itself with a variation of shortest path. For the purpose of question, if a particular path from $x$ to $y$ is $x → a → b → c → y$, then we refer to $a,b,$ and $c$ as lay-over nodes for that particular path. Now your question: Design an efficient algorithm that finds the shortest weighted distance between two given nodes $s$ and $t$, with the additional requirement: there is a cost associated with lay-over nodes. You can visit up to two lay-over nodes for free,but every additional lay-over will incur a fee. Let $c(k)$ the cost associated with the $k$ node on the path.

Dijkstra(G, s,t):
    Q = ∅       # create priority queue
    dis[s] = 0
    for each vertex v in G: 
        if v != s
            dis[v] = ∞
        π(v) = nil
        hop[v] = 0
        c[v] = 0
        Q.enqueue(dis[v])      # set all vertices in Q

    While Q not empty:
        u ← extractMin(Q)
        for each neighbor v of u:
            hop[v] = hop[u]+1
            if hop[v] >= 3     # check if lay-over/hops more or equal to 3
                c[v] = c[v] + hop[v]
            alt = d[u] + w(v,u) + c[v]
            if d[v] > alt
                d[v] = alt
                π(v) = u
                Q.decrease_priority(v, alt)

    # retrieve the path from s to t
    Stack S = ∅             # create a stack
    Push (S, t)
    v ← Top(S)
    while  π(v) != nil 
        Push (S, π(v))
        v = π(v)
    return S      # The path is stored in the stack S from top to bottom. 
End