CODEWITHSUNDEEP
algorithmgraph
Epitheoritis 32
Epitheoritis 32

Reputation: 366

Shortest paths problem with two conditions

Let's say i have a directed graph G(V,E,w,c) where w is the positive weight of each edge and c is the cost of every edge being either 1 or 0.I need to find an algorithm that for given source vertice u finds the shortest paths from u to every vertice in V that have cost ≤ k(where k≥1).

I tried modifying Bellman ford's algorithm but i can't seem to find the solution.

Upvotes: 1

Views: 618

Answers (1)

btilly
btilly

Reputation: 46497

Let me restate my understanding of the problem.

For all vertices that you can reach with a cost of no more than k, you want the path of minimal weight that gets there from a vertex u.

You need a combination of ideas to get there.

Suppose that a RouteToNode object has the following attributes: cost, weight, node, lastRouteToNode and an autoincrementing id. This is a linked list carrying us back to the original node, letting us reconstruct the route. We compare them by cost, then weight, then id.

We have a hash/dictionary/whatever you want to call it that maps nodes to the lowest weight RouteToNode object reaching that node. Call it bestRoute.

We have a todo list that has RouteToNodes that we have not yet processed which is a priority queue that always returns the minimal RouteToNode. Note that it always returns them from lowest cost to highest.

We start with bestRoute having nothing in it, and a todo queue with only a single RouteToNode, namely:

{
    id: 0,
    cost: 0,
    weight: 0,
    node: u,
    lastRouteToNode: null
}

And now we execute the following pseudocode:

while todo is not empty:
    thisRouteToNode = todo.pop()
    if thisRouteToNode.node not in bestRoute or
      thisRouteToNode.weight < bestRoute[thisRouteToNode.node].weight:
        bestRoute[thisRouteToNode.node] = thisRouteToNode
        for edge adjacent to thisRouteToNode.node:
            construct nextRouteToNode by adding edge
            if nextRouteToNode.cost <= k:
                todo.push(nextRouteToNode)

Upvotes: 1

Related Questions