graph - Shortest path with Vertex Weight

问题:

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?

回答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'

回答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.