Introduction

Most shortest-path problems put costs on edges, but some problems assign cost to visiting vertices instead. The good news is that you usually do not need a completely different algorithm: with nonnegative vertex weights, you can adapt Dijkstra's algorithm directly or transform the problem into an ordinary edge-weighted graph.

Define the Cost Model First

Before choosing an algorithm, decide exactly what path cost means. Different problems use different conventions:

• include the source vertex cost
• include the destination vertex cost
• include every visited vertex cost
• exclude the source because you start there "for free"

For this article, assume path cost is the sum of all visited vertex weights, including both source and destination.

That convention affects the initialization and the relaxation formula, so it should never be left implicit.

Convert Vertex Cost Into Transition Cost

A simple way to think about the problem is: moving from u to v costs the weight of entering v.

Under that interpretation:

• the source distance starts as weight[source]
• relaxing an edge from u to v uses dist[u] + weight[v]

This turns a vertex-weight problem into something very close to an ordinary shortest-path computation.

Dijkstra for Nonnegative Vertex Weights

If all vertex weights are nonnegative, Dijkstra's algorithm still works.

1import heapq
2
3
4def shortest_path_with_vertex_weights(graph, weights, source):
5    dist = {node: float('inf') for node in graph}
6    dist[source] = weights[source]
7
8    pq = [(dist[source], source)]
9
10    while pq:
11        current_dist, u = heapq.heappop(pq)
12        if current_dist != dist[u]:
13            continue
14
15        for v in graph[u]:
16            candidate = dist[u] + weights[v]
17            if candidate < dist[v]:
18                dist[v] = candidate
19                heapq.heappush(pq, (candidate, v))
20
21    return dist
22
23
24graph = {
25    'A': ['B', 'C'],
26    'B': ['D'],
27    'C': ['D'],
28    'D': []
29}
30
31weights = {
32    'A': 1,
33    'B': 2,
34    'C': 3,
35    'D': 4
36}
37
38print(shortest_path_with_vertex_weights(graph, weights, 'A'))

In this graph:

• 'A -> B -> D costs 1 + 2 + 4 = 7'
• 'A -> C -> D costs 1 + 3 + 4 = 8'

So the shortest path from A to D goes through B.

The More Formal Graph Transformation

In graph theory discussions, you may also see each vertex split into two nodes:

• 'v_in'
• 'v_out'

Then you add one directed edge from v_in to v_out whose weight equals the original vertex weight. Original graph edges are rewired so they go from u_out to v_in.

That construction converts the vertex-weight problem into a standard edge-weight problem without changing shortest-path structure.

It is useful when you want to reuse a black-box shortest-path routine or prove correctness formally, but it is often more cumbersome to implement than the direct Dijkstra relaxation rule.

What Changes if Edge Weights Also Exist

Sometimes a graph has both edge weights and vertex weights. In that case, you must be explicit about the relaxation formula.

A common model is:

candidate = dist[u] + edge_cost(u, v) + weight[v]

The principle is the same. You just pay both the travel cost and the destination-vertex cost.

This is where a lot of confusion starts, because people mix conventions halfway through the solution. Pick one cost definition and apply it consistently.

Negative Vertex Weights Need a Different Algorithm

Dijkstra relies on nonnegative transition costs. If vertex weights can be negative, then the effective edge costs can also be negative, and Dijkstra is no longer valid.

In that case, use an algorithm designed for negative weights, such as Bellman-Ford, and also check whether your transformed graph introduces a negative cycle under the chosen cost convention.

The rule is the same as in ordinary edge-weight shortest paths: algorithm choice depends on whether the effective transitions can go negative.

Common Pitfalls

One common mistake is forgetting whether the source vertex cost is included. That changes the initialization and every reported path total.

Another is mixing vertex and edge costs inconsistently. If both exist, your recurrence must say exactly where each one is charged.

People also sometimes apply Dijkstra even when negative vertex weights are allowed. Once the effective transition costs can be negative, that assumption breaks.

Finally, do not switch conventions midway through the problem. If one paragraph includes the source cost and the next does not, the final answer will be off even if the algorithm is otherwise correct.

Summary

• Vertex-weight shortest paths can often be solved with standard shortest-path ideas.
• For nonnegative vertex weights, Dijkstra works if relaxation adds the destination vertex cost.
• Be explicit about whether source and destination costs are included.
• Splitting each vertex into an in-node and out-node is the formal graph transformation.
• If effective transition costs can be negative, choose an algorithm that supports negative weights.