Relax Function on Shortest Path Algorithm

In a Weighted Directed Graph G (with positive weights), with n vertex and m edges, we want to calculate the shortest path from vertex 1 to other vertexes. we use 1-dimensional array D[1..n] , and D[1]=0 and others filled with +infinity . for updating the array we just permit to use Realx(u, v)

if D[v] > D[u] + W(u, v) then D(v):=D(u)+W(u,v) 

in which W(u, v) is the weight of u-->v edge. how many time we must call the Relax function to ensure that for each vertex u , D[u] be equals to length of shortest path from vertex 1 to u .

Solution: i think this is Bellman-Ford and m*n times we must call.

In Dijkstra and Bellman-Ford and others, we have Relax function. How do we detect which of them?

Cited from CLRS Book:

The algorithms in this chapter differ in how many times they relax each edge and the order in which they relax edges. Dijkstra's algorithm and the shortest-paths algorithm for directed acyclic graphs relax each edge exactly once. The Bellman-Ford algorithm relaxes each edge |V|-1 times.

---

For Bellman-Ford and Dijkstra algorithm, we will use same relax function, but the main different is, how many times the relax function is being called, in each algorithm.

For Bellman-Ford:

for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           relax(u,v)

So, relax function will be called exactly n - 1 times for each edges.

For Dijkstra:

while Q is not empty:
      u ← vertex in Q with min dist[u]  // Source node in first case
      remove u from Q 

      for each edge(u,v) of u:           // where v is still in Q.
          relax(u,v)

      end for
end while

In this case, relax function will be called once for each edge, when its starting vertex is processed.

Summary: Bellman-Ford's algorithm, the number of relax function call is m*n , and Dijkstra's algorithm, the number of call is m , with m is number of edges, and n is number of vertices.

Note : code is taken and modified from Wikipedia to bring you clearer view of using relax function

---

We should iterate over each edge n - 1 times:

for step <- 0 ... n - 1:
    for edge <- edges
         relax(edge)

It is necessary: imagine a chain with n vertices. We need to make exactly n - 1 steps to reach the last.

It is sufficient: there no cycle in an optimal path, and the longest simple path contains at most n - 1 edges.

So the answer is (n - 1) * m is want to simply iterate over the distance array and make changes(yes, it is Ford-Bellman's algorithm).

However, if another algorithm is used(for instance, Dijkstra's), the number of calls to the relax function is less(namely, m ).

So it depends on details of the algorithm we are using.

链接地址: http://www.djcxy.com/p/35302.html

上一篇: 如何为未加权图做最短路径算法？

下一篇: 放松函数最短路径算法