Thread: Can someone explain to me ?

Hello,
I am messaging you because i have to can an algorithm but i do not understand it at all. I am not asking for the solution, i want to try it myself but i can not try if i don't get it haha.

Can someone explain me what i should do please ?

Here are my intructions :
(Down)

I don't know what the algorithm should do


Thanksss

--- Update ---

https://goopics.net/a/g97H8NT5

I sent links because there is some images.

Without the images this is :

Introduction:
Digraph D = (V;A;T) composed of a set V of n nodes, a set A of m directed arcs and T set of T time
steps. 𝑡𝑖𝑗 𝑑𝑒𝑛𝑜𝑡𝑒𝑠 travel time/delay of arc (i; j) and cij represents capacity of arc (i; j).
An o-d path is an ordered set of arcs {(i0; i1); (i1; i2); (i2; i3); : : : ; (ik−1; ik )} such that i0 = o, ik =
d and (𝑖𝑙; 𝑖𝑙 + 1) ∈ 𝐴; ∀ 𝑙 = 0; . . . ; 𝑘 − 1.



Lazy version of the Chen's algorithm:
The so-called lazy version of the Chen's algorithm is used for solving the K-quickest loopless paths
problem as presented in the works of Pascoal et al. [1-2]. The problem requires the identification
of best K elementary quickest paths provided in an increasing order of their transmission time.
This is the time required to transship an item from source to sink.
The idea underlying the method is to reduce the problem to several computations of a state-ofthe-art K-shortest loopless path algorithm and to alternate path identification steps to path
selection steps till a total of K paths are identified. A pseudocode of the algorithm is provided in
Algorithm 1.


Algorithm 1 :

Input: D=(V,A,T), (o,d);
Output: The K quickest path in D;

1: Initialization
a. Order arc capacities c1,...,cr;
b. A' <- A;
for l=1,...,r;
A' <- {(i,j) € A' | cij >= cl };
L[l] <- the o-d shortest loopess path in D'=(V,A'), 0 otherwise;

2: Fint K-Quickest Paths
k <- 0;
while k<K and Ǝ l s.t L[l] =/= 0 do:
a. p <- L[l] s.t L[l] = argmin(i=1,...,r) T(L[i]);
b. A' <- {(i,j)€ A | cij >= cl};
L[l] <- the next o-d shortest loopless path in D'=(V,A'), 0 otherwise;
C. if k=0 or p €/€ {p'1,...,p'k} then k <- k+1, p'k <- p;

3. Return {p'1...,p'k};




It requires as an input the dynamic digraph and the given o-d (source-sink) to be transshipped. In
the initialization phase, Step 1, it lists all the arc capacities in an increasing order excluding
potential repetitions, hence obtaining r different values with r≤m. Then, for each of these values
it constructs a subgraph by considering only arcs whose capacities exceed or are equal to the
given value set as a lower bound and in the so-constructed digraph it identifies the shortest
loopless path w.r.t. arc travel times, Step 1b. The generated shortest paths are stored in the
array L.
In Step 2, the algorithm iteratively selects the best shortest path in the array w.r.t. the
transmission time and replaces it by the next shortest loopless path found in the related
subgraph. At this stage any algorithm for solving the K shortest loopless path problem can be
employed, such as the Yen's algorithm [3] or Katoh et al. [4]. The procedure stops
whenever K different paths have been selected or no more shortest paths are available.

I can't open the file you attached.