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 can just 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 must we call the relax function to ensure that for each vertex u, D[u] 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.
Could anyone help me? In Dijkstra and Bellman-Ford and others we have Relax functions. How do we detect which one of them?
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.
Hello,
I will try to give you the answer for the Dijkstra algorithm. From what I remember, you only need to relax each edge at most once, as stated in your question. Here is why. Starting with vertex 1, let's assume it is connected to vertices v_1,...v_i. The relaxing function will write for all k in {v_1,...,v_i}, D[k]=W(1,k). Then, you consider that vertex 1 is out of the graph, and apply the same function on vertex v_j such that D[v_j] is minimal in D (except for D[1]). Without loss of generality, v_j, has edges to vertices {v_l,...v_z}. For k' in {v_l,...v_z}, the function writes: D[k']=min(D[k'],D[v_j]+W(v_j,k)). Once this is done for all k', v_j is taken out of the graph, and the function is applied to the vertex v_p that has minimal D[v_p] (except for D[1] and D[v_j]).
By iterating this process, you will end up:
- applying the function only once to each vertex. Since each vertex is taken out after the function is applied on it, each edge is relaxed exactly once in a non-directed graph, and at most once in a directed graph (depending on whether or not you have vertices linked by a double edge, with one in each direction).
- with for all k in [|1,n|], D[k] is the cost of the shortest path from vector 1 to vector k.
This algorithm can be used in a more general way in the presence of cyclic graphs, when looking for the shortest cycle. In this case the complexity is a bit higher.
The wikipedia article on Dijkstra's algorithm is a good resource to understand it : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
I hope this answers your question.
In other terminology, every edge or nodes is serviced only once. This applied to all network graph such as Vehicle Routing Problem (VRP) and CRP (Capacitated Arc Routing Problem).
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering