2

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:

1 2 1
1 3 5
2 4 5
3 4 5
4 6 2

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.

Improve this question
22
  • 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. Commented Mar 8, 2014 at 16:10
  • 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) Commented Mar 8, 2014 at 16:22
  • But then you have positive weights. You can just transform the graph prior to finding the shortest path. Commented Mar 8, 2014 at 16:27
  • I said that i don't know if weights are positive :) I don't know anything about weights and cycles Commented Mar 8, 2014 at 16:33
  • 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. Commented Mar 8, 2014 at 16:36

2 Answers 2

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

-1

To solve this kind of problem you can use a min/max flow type approach.

For every node you have two possible conditions: you either know fastest way to get to that node or you do not. So, you can tag each node with a number, or with null if it is unknown what the least cost is for that node.

In the beginning you only know the least cost for the nodes adjacent to the starting node, so you fill those in.

Now, propagating forwards you can find out the least cost for the nodes adjacent to those and so on, until you have filled in the whole graph.

Improve this answer

21 Comments

The thing is that I don't really know the cost for the adjacents if I dont know the next nodes on the path. I need to know 3 nodes to compute the path weight.
Fine, then in that case you compute the minimums for each node TWO steps away from the starting node and propagate forwards from there. The principle is the same.
For any kind of problem like this, create a non-trivial example on paper and then manually fill in the minimums as you go. It's like sudoku. Once you have done it manually, it should be clear how to write a program to do it.
The cost of a node depends also on the edge you take next, so it's not sufficient to aggregate on path prefixes like in dijkstra. You simplify the problem to a degree where it has nothing to do with the original problem anymore and then you say without justification that it's simple to adapt totally unrelated ideas to the problem like max flow. I don't get how this is helpful. Have you thought this through?l
@Niklas B.Gah, it's Niklas again. First of all, for any graph where the test value is a combination of two edges you can convert the graph to a new graph where every edge in the new graph equates to a possible combination of edges in the original graph. So, you can certainly solve this problem by converting the graph and using Warshall. Secondly, the method I describe above will work perfectly well and is somewhat easier than doing the graph conversion. Neither of the methods has anything to do with the Djikstra algorithm.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.