Dynamic programming efficient network

Question

Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting vertex u to ending vertex v, with the constrain that the vertices and edges will have an equal or higher predefined value. For example the highest rate of data in a network,

i.e. the vertices A,B,C,D and E with values unlimited,6,2,5 and unlimited respectively, also the edges A->B, A->C, B->D, C->D and D->E with values 4,3,5,8 and 10 respectively. In this case the most efficient path from A to E would be A->B, B->D, D->E.

Could someone provide some pseudo-code or any thoughts, thank you in advance.

My main concern because is not like an implementation issue. So what I am thinking: Find the longest path in DAG with Dijkstra's, and some tweaks (multiply the weights of the edges with -1, finding shortest path and then multiplying again with -1 for longest), however I should fit in the values of the vertices to.

Answer 1

You can use a modified version of Dijkstra's Algorithm with 3 modifications.

First of all you change all the weights from w to (W-w) where W is some large value. Since your case is an acyclic graph, I don't think you need Bellman-Ford algorithm.

The update step in Dijkstra's looks somewhat like this for a vertex v which is adjacent to u

if dst[v] > dst[u] + weight[(u,v)]
    dst[v] = dst[u] + weight[(u,v)]

You should modify this to include the vertex weights.

if dst[v] > dst[u] + weight[(u,v)] + weight[u]
    dst[v] = dst[u] + weight[(u,v)] + weight[u]

Also in Dijkstra, you store the predecessor in the shortest path for each vertex. In your case, you should store a set of predecessors because you are looking for multiple shortest paths.

At the end you can consider all the shortest paths(longest originally) and select the one with least hops.