Modified shortest path algorithm

Question

I've been looking for solution but got stuck.

I need to find shortest path in undirected graph. As input I got set of undirected edges (x,y,p) where x and y are nodes and p which is weight of the edge between x and y.

The length of a path is defined as the sum of of absolute differences between adjacent edges of each node.

Example edges:

There are multiple paths from 1 to 6:

1 -> 2 -> 4 -> 6   weight = |5 - 1| + |2 - 5| = 7
1 -> 3 -> 4 -> 6   weight = |5 - 5| + |2 - 5| = 3

Thus the shortest path has length 3, which should be the output of the algorithm.

Are the weights on the nodes or the edges? It sounds like you have node weights and use absolute difference as edge weights. In that case you can use Dijkstra. — Silas
Weights are on the edges, in excercise it is defined that to compute weight of node f.e y where there is a path x->y->z then weight of the y =|xy -yz| (xy is weight of the edge between x and y nddes) — B.W
But then you have positive weights. You can just transform the graph prior to finding the shortest path. — Silas
I said that i don't know if weights are positive :) I don't know anything about weights and cycles — B.W
You use the absolute difference to find the cost of a path, so you have non-negative weights since the absolute difference is non-negative. — Silas

Niklas B. Niklas B. · Accepted Answer · 2014-03-08T23:52:31

You can use Dijkstra on edges instead of nodes and it will work. Let s be the source node and t be the target. w(i,j) be the weight of the edge (i,j).

d(i,j) = infinity for all edges (i,j)
q = new empty priority queue, ordered by d
for all edges (s,x):
    d(s,x) = 0
    insert (s,x) into q
while q is not empty:
    (x,y) = q.dequeue
    for all edges (y,z):
        if z != x and d(x,y) + |w(x,y) - w(y,z)| < d(y,z):
            d(y,z) = d(x,y) + |w(x,y) - w(y,z)|
            insert (y,z) into q

The result will be the minimum distance of an edge (x,t). The runtime is O(m * log m) if the priority queue is implemented as a binary heap.

Modified shortest path algorithm

2 Answers