graph - Shortest path with Vertex Weight

Question

Here is an excise:

In certain graph problems, vertices have can have weights instead of or in addi- tion to the weights of edges. Let Cv be the cost of vertex v, and C(x,y) the cost of the edge (x, y). This problem is concerned with finding the cheapest path between vertices a and b in a graph G. The cost of a path is the sum of the costs of the edges and vertices encountered on the path.

(a) Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of ∞).Assume that Cv =1 for all vertices 1≤v≤n (i.e.,all vertices have the same cost). Give an efficient algorithm to find the cheapest path from a to b and its time complexity.

(b) Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an efficient algorithm to find the cheapest path from a to b and its time complexity.

(c) Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path from a to b and its time complexity.

---

Here is my answer:

(a) use normal BFS;

(b) Use dijkstra’s algorithm, but replace weight with vertex weight;

(c)

Also use dijkstra’s algorithm

If only considering about edge weight, then for the key part of dijkstra's algorithm, we have:

if (distance[y] > distance[v]+weight) {
    distance[y] = distance[v]+weight; // weight is between v and y
}

Now, by considering about vertex weight, we have:

if (distance[y] > distance[v] + weight + vertexWeight[y]) {
   distance[y] = distance[v] + weight + vertexWeight[y]; // weight is between v and y
}

---

Am I right?

I guess my answer to (c) is too simple, is it?

Solution 1

You are on the right track, and the solution is very simple.

In both B,C, Reduce the problem to normal dijkstra, which assumes no weights on the vertices.
For this, you will need to define w':E->R, a new weight function for edges.

w'(u,v) = w(u,v) + vertex_weight(v)

in (b) w(u,v) = 0 (or const), and the solution is robust to fit (c) as well!

The idea behind it is using an edge cost you the weight of the edge, and the cost of reaching the target vertice. The cost of the source was already paid, so you disregard it¹.

Reducing a problem, instead of changing an algorithm is usually much simpler to use, prove and analyze!.

---

(1) In this solution you "miss" the weight of the source, so the shortest path from s to t will be: dijkstra(s,t,w') + vertex_weight(s)_ [where dijkstra(s,t,w') is the distance from s to t using out w'

Solution 2

The vertex weight can be removed by slicing every vertex a in two vertices a1 and a2 with an edge from a1 to a2 with the weight of a.

I think you are right for the adaptation of dijkstra’s algorithm.

Comments

[Jackson Tale]

I think in (a), vertices have equal weights, and edges don't have weights. we can just use normal BFS right?

[amit]

@JacksonTale If I understand the problem correctly - you are absolutely right regarding (a), I didn't mention anything in the answer about this part because I have nothing to add on what you have already done!

[Jackson Tale]

sorry, I just saw you said in both a, b, reduce...to normal dijkstra. I thought my (a) had problem. :D thanks for clarifying.

[Jackson Tale]

And also Reducing a problem, instead of changing an algorithm is usually much simpler to use, prove and analyse!. this is very inspiring!

[amit]

@JacksonTale Oh yea, it was a typo - sorry, I meant both b and c. Keep a as it is! :)

[Jackson Tale]

Thanks for your answer, @amit

[Jackson Tale]

could you please help me with this one? stackoverflow.com/questions/10456935/…

[zengr]

@amit How would you solve the same problem C for an undirected graph?

[amit]

@zengr: For each undirected edge (u,v) in the original graph, add two edges in the new graph: (u,v) such that w'(u,v)=w(v) and (v,u) such that w'(v,u)=w(u). Given this new graph - run dijkstra's algorithm and get your shortest path in the original graph.

[zengr]

But where do you take the weight on the undirected edges into consideration? The problem states: for an undirected graph with node weight=w(u) and edge weight=w(u,v). Compute the shortest path.

[amit]

@zengr: In this case use both: for each edge (u,v) in the original undirected graph: create two edges in the reduced graph: (u,v) and (v,u) with weights: w'(u,v) = w(v) + w(u,v), w'(v,u) = w(u) + w(v,u). Don't forget to add w(s) [where s is the source node] to the total length of the path.

[zengr]

Regarding your last statement about w(s), why should I do that? I will anyway account for that when I say: w(u,v) + w(u) while starting out?

[amit]

@zengr The shortest path you will find is s->u1->u2->...->un, which will give you total weight of w'(s,u1) + ... + w'(un-1,un) = w(s,u1) + w(u1) + w(u1,u2) + w(u2) + ... + w(un-1,un) + w(un) It does not count the weight of the first node in path, so just add it during post processing, it can be done easily. It does not violate correctness because all paths in G' are missing the exact same factor.

[Christian Long]

I don't think this will work. If a is adjacent to b, c, and d, then what will a1 and a2 be adjacent to?

[Ankit Roy]

Maybe you could point out in the answer that if the input graph is undirected (which I would assume is the case here) then edges need to be "doubled"? In any case, a trick that avoids converting to a directed graph with twice as many edges for (b) and (c) is to make each edge weight the sum of its endpoint vertex weights: Now every a-b path has (nearly) double the weight ;) (You can make it exactly double by adding w(a) to every edge incident on a and similarly for b, though this doesn't affect the path found as a solution as it changes all simple a-b paths by the same amount.)