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

Re: Can someone explain to me ?

Please post the text that you have questions about here on the forum, not at a link.

Re: Can someone explain to me ?

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.

Re: Can someone explain to me ?

You should ask your instructor about the problems you are having.

If you have any java programming questions, post them here.