Graph - Самый короткий путь с вершиной Вес

Вот акциз:

В некоторых задачах графа вершины могут иметь вес вместо или в дополнение к весам ребер. Пусть Cv - стоимость вершины v и C (x, y) - стоимость ребра (x, y). Эта проблема с нахождением дешевого пути между вершинами a и b в графе G. Стоимость пути - это сумма затрат на ребра и вершины встречается на пути.

(a) Предположим, что каждое ребро в графе имеет вес нуля (в то время как не-ребра имеют стоимость ∞). Предположим, что Cv = 1 для всех вершин 1≤v≤n (т.е. все вершины имеют одинаковую стоимость). Дайте эффективный алгоритм для найти самый дешевый путь от a до b и его временную сложность.

(b) Предположим теперь, что затраты вершин не являются постоянными (но все они положительный), а краевые затраты остаются такими же, как указано выше. Дайте эффективный алгоритм, чтобы найти самый дешевый путь от a до b и его время сложность.

(c) Предположим теперь, что затраты на ребро и вершину не постоянны (но все они положительные). Дайте эффективный алгоритм для поиска дешевый путь от a до b и его временная сложность.

Вот мой ответ:

(a) использовать обычную BFS;

(b) Используйте алгоритм dijkstras, но замените вес вершинным весом;

(c)

Также используйте алгоритм dijkstras

Если учитывать только размер края, то для ключевой части алгоритма dijkstra имеем:

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

Теперь, рассмотрев вопрос о весе вершин, имеем:

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

Я прав?

Я думаю, мой ответ на (c) слишком прост, не так ли?

Ответы

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