Dear jumpstart,
1.
This proof is indeed a terse one, leaving out so much detail as to
be incomprehensible on first sight. After reading it over many times,
however, I came to understand what calculations are missing.
The proof of Theorem II.1 begins by stating Lemma II.1, which is itself
unproven. This lemma contains two separate statements that I shall
prove independently.
First, the lemma claims the following.
Let P_tau(v) denote the cheapest path from the source to any vertex v
in G_tau satisfying the delay constraint tau. The cost of P_tau(v) is
no more than the cost of the cheapest path between s and v satisfying
the delay constraint T in G.
The claim says, in effect, that no path P_tau(v) can possibly cost more
than the path P(v) computed by DAD(G,T) in the original graph. To see
why this is so, consider that the path P(v) consists of k hops with
costs c_1, c_2, ..., c_k. By definition, the sum of these costs is no
greater than the delay threshold T.
c_1 + c_2 + ... + c_k <= T
If we take the same path through the tau-scaled graph G_tau, each of
these costs is multiplied by tau/T and truncated to an integer. In other
words, we take the floor of tau/T*c_i for each i from 1 to k. Hence,
each cost in the tau-scaled graph is no greater than T/T*c_i.
floor(tau/T*c_1) + floor(tau/T*c_2) + ... + floor(tau/T*c_k)
<= tau/T*c_1 + tau/T*c_2 + ... + tau/T*c_k
= tau/T * (c_1 + c_2 + ... + c_k)
<= tau/T * T
= tau
The cost of the path P(v) in the tau-scaled graph G_tau is therefore no
greater than tau. But if P_tau(v) is the cheapest path whose delay does
not exceed tau, then the cost of P_tau(v) cannot be greater than that
of P(v), which is itself a path whose delay does not exceed tau.
The second claim in Lemma II.1 follows.
Further, the delay of P_tau(v) in G is at most T(1 + D/tau) where D
is the maximum length, in hops, of any cheapest path satisfying the
delay constraint tau.
Consider that the path P_tau(v) consists of j hops such that j <= D,
and name the costs of the hops d_1, d_2, ..., d_j, so that the total
cost of P_tau(v) in the tau-scaled graph G_tau is the following.
d_1 + d_2 + ... + d_j <= tau
Let us add j to each side of the inequality, then multiply each side
by T/tau.
(d_1+1) + (d_2+1) + ... + (d_j+1) <= tau + j
T/tau*(d_1+1) + T/tau*(d_2+1) + ... + T/tau*(d_j+1) <= T + j*T/tau
Now observe that each term T/tau*(d_i+1) is at least as great as the
corresponding cost c_i in the original graph G.
d_i = floor(tau/T*c_i)
d_i+1 >= tau/T*c_i
T/tau*(d_i+1) >= c_i
Hence, the following obtains.
c_1 + c_2 + ... + c_j
<= T/tau*(d_1+1) + T/tau*(d_2+1) + ... + T/tau*(d_j+1)
<= T + j*T/tau
But c_1 + c_2 + ... + c_j is just the total cost of P_tau(v) in G. And
since D is an upper limit on j, this total cost can be no greater than
the following.
T + D*T/tau = T(1 + D/tau)
That concludes the proof of the lemma.
The theorem then stipulates that tau >= D/e, with the following
consequence for the cost of P_tau(v) in G.
D/e <= tau
T(1 + D/tau) <= T(1 + D/(D/e)) = T(1 + e)
This guarantees that the algorithm DSA will terminate. Since the only
variable amount of work done by DSA is in the call to subroutine DAD,
the runtime of DSA is governed by that of DAD. And DAD, for its part,
takes time proportional to mT, where T is the input delay threshold and
m is the number of nodes in the input graph.
On its first iteration, DSA calls DAD with delay threshold tau_0, for a
cost of m*tau_0. On the second iteration, the delay threshold doubles
to 2*tau_0, for a cost of 2*m*tau_0, and so on. We can simplify the
resulting series as follows.
m*tau_0 + m*2*tau_0 + ... + m*2^k*tau_0
= m*tau_0* (1 + 2 + ... + 2^k)
= m*tau_0 * (2^(k+1) - 1)
< m*tau_0 * 2^(k+1)
= 4*m * tau_0*2^(k-1)
< 4*m * D/e
We drop the constant 4 to obtain an asymptotic runtime of O(m*D/e).
2.
A succinct description of Dijkstra's Shortest Paths algorithm is given
on the following web page.
Dijkstra's algorithm keeps two sets of vertices:
S the set of vertices whose shortest paths from
the source have already been determined and
V-S the remaining vertices.
The other data structures needed are:
d array of best estimates of shortest path to each vertex
pi an array of predecessors for each vertex
The basic mode of operation is:
1. Initialise d and pi.
2. Set S to empty.
3. While there are still vertices in V-S:
1. Sort the vertices in V-S according to the
current best estimate of their distance from
the source.
2. Add u, the closest vertex in V-S, to S.
3. Relax all the vertices still in V-S connected to u
University of Western Australia: John Morris: Dijkstra's Algorithm
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
Observe that the main loop of the algorithm, labeled above with the outer
number 3, runs once for each vertex in the graph. Thus, the main loop runs
n times. We can neglect the outer Steps 1 and 2, which take constant time.
The inner Step 1 requires that we find the closest remaining vertex
to the vertices in S, which takes no more than log n operations if we
store and update the vertex distances in a heap. Thus, the inner Step
1 contributes O(n log n) runtime to the total.
The inner Step 2 takes a constant amount of time.
The inner Step 3 is interesting because it requires, for each vertex
chosen from the remaining vertices, that we consider each edge incident
on it. How many times, then, do we look at each edge? Since each vertex
is treated only once, and an edge connects two vertices, each edge of
the graph is considered twice in the course of the algorithm. Thus, the
cost of relaxing u's neighbors -- which are just the vertices neighboring
it along the incident edges -- is 2m in total, or asymptotically O(m).
Hence, the total cost of executing Dijkstra is
O(n log n) + O(m) = O(m + (n log n)).
It has been a pleasure to address this question on your behalf. If
you find fault with any part of my answer, please inform me through a
Clarification Request so that I may fully meet your needs before you
assign a rating.
Regards,
leapinglizard |
Request for Answer Clarification by
jumpstart-ga
on
06 Apr 2005 23:28 PDT
Dear LeapingLizard,
First of all, I appreciate for your taking time to explain me the answer...
However, I've asked for the refund as some of the *MAJOR* errors in
your explanation
made me have a *BAD* day :(
I am sorry that there was no time for asking clarification and hearing
back from you
as I was needing it ASAP...as I mentioned in my Question.
Just a word of thought,
There is no need for clarification again. In case if you feel, that
you can clarify and
re-post some of the following issues before this question gets closed, that might
really help someone in future, who might refer to it :)
<<<<Quoting your answer>>>>
----
""""The claim says, in effect, that no path P_tau(v) can possibly cost more
than the path P(v) computed by DAD(G,T) in the original graph. To see
why this is so, consider that the path P(v) consists of k hops with
costs c_1, c_2, ..., c_k. By definition, the sum of these costs is no
greater than the delay threshold T.
c_1 + c_2 + ... + c_k <= T""""
----
The paper never mentioned that sum of the <<<costs??>>> is no
greater than the delay threshold T. It should probably be delay...I guess
----
""""If we take the same path through the tau-scaled graph G_tau, each of
these costs is multiplied by tau/T and truncated to an integer. In other
words, we take the floor of tau/T*c_i for each i from 1 to k. Hence,
each cost in the tau-scaled graph is no greater than T/T*c_i.
floor(tau/T*c_1) + floor(tau/T*c_2) + ... + floor(tau/T*c_k)
<= tau/T*c_1 + tau/T*c_2 + ... + tau/T*c_k
= tau/T * (c_1 + c_2 + ... + c_k)
<= tau/T * T
= tau""""
----
Again, costs never get multiplied by tau/T....or truncated and so on
and so-forth...
Also,....."""Hence, each cost in the tau-scaled graph is no greater
than <<<<T/T*c_i.>>>""""
[should be tau/T*c_i]
----
""""The cost of the path P(v) in the tau-scaled graph G_tau is therefore no
greater than tau. But if P_tau(v) is the cheapest path whose delay does
not exceed tau, then the cost of P_tau(v) cannot be greater than that
of P(v), which is itself a path whose delay does not exceed tau.""""
----
This is again wrong.....as it talks about cost..."The cost of the path <<<P(v)>>>
[I guess, it should be P_tau(v) ] in the tau-scaled graph G_tau is
therefore no greater than tau"
"""which is itself a path whose delay does not exceed tau.""" which
is totally misleading!!
----
""""Consider that the path P_tau(v) consists of j hops such that j <= D,
and name the costs of the hops d_1, d_2, ..., d_j, so that the total
cost of P_tau(v) in the tau-scaled graph G_tau is the following.""""
----
Again, it should be delays, instead of costs.
----
""""Now observe that each term T/tau*(d_i+1) is at least as great as the
corresponding cost c_i in the original graph G.""""
----
Same error!
----
""""The theorem then stipulates that tau >= D/e, with the following
consequence for the cost of P_tau(v) in G.""""
----
Why suddenly D/e? where does that come from?
Also, """consequence for the cost of P_tau(v) in"""....should be delay
----
= 4*m * tau_0*2^(k-1)
< 4*m * D/e
----
What happened to the k value ? How the paper says k = ceil (log [d/e]/tau_0) ?
How all of a sudden tau_0*2^(k-1) < D/e ??
And, the answer to the question number 2 is surely above average but
not that much satisfactory!
I understand that confusing between delay and costs everywhere in your
answer is not that big a deal,
if I already knew that's what going on.
But, still you must realize this is DSA's complexity, which is
basically DELAY SENSITIVE ALGORITHM
and that makes its true explanation more important.
I didn't really mean to get the full refund. I wanted to give at least
half the price for your answer,
and I came to know that every refunded answer gets 50% to the researcher however.
Anyways, I am totally sorry!!
Just thought that you should know...the reasons..
Once again, thanks for all your hard work and please don't mistake me!
-JumpStart
|
