The Algorithm Design Manual Second Edition

Analysis

What is the running time of Dijkstra’s algorithm? As implemented here, the com-

plexity is O(n

2

). This is the same running time as a proper version of Prim’s

algorithm; except for the extension condition it is the same algorithm as Prim’s.

The length of the shortest path from start to a given vertex t is exactly the

value of distance[t]. How do we use dijkstra to find the actual path? We follow

the backward parent pointers from t until we hit start (or -1 if no such path

exists), exactly as was done in the find path() routine of Section

5.6.2

(page

165

).

Dijkstra works correctly only on graphs without negative-cost edges. The reason

is that midway through the execution we may encounter an edge with weight so

negative that it changes the cheapest way to get from s to some other vertex

already in the tree. Indeed, the most cost-effective way to get from your house

to your next-door neighbor would be repeatedly through the lobby of any bank

offering you enough money to make the detour worthwhile.

Most applications do not feature negative-weight edges, making this discus-

sion academic. Floyd’s algorithm, discussed below, works correctly unless there are

negative cost cycles, which grossly distort the shortest-path structure. Unless that

bank limits its reward to one per customer, you might so benefit by making an

infinite number of trips through the lobby that you would never decide to actually

reach your destination!