calcul de la complexité d'un algorithme de Djikstra

bonjour, aidez moi s'il vous plait pour le calcul de la complexité de l'algorithme suivant:


Algorithme proposé par [51]pour trouver quelques arcs strictement forts

1. Appliquant l’algorithme de Djikstra à G sous le scénario s on obtient un plus court chemin p de 1 à m.

2. Choisir un arc (k, r) 2 A(p).

3. Construire un scénario s0 pour lequel ls0
ij = lij .si(i, j) 2 A(p) et ls0
ij = lij si (i, j) /2 A(p)

4. Appliquant l’algorithme de Djikstra à G−(k, r) sous le scénario s0 . S’il existe un plus court chemin q0 de 1 à m, Aller à (5). Sinon (k, r) est strictement fort.

5. Calculer ls0
q0 et ls0
p .

6. Sils0
q0 > ls0
p alors l’arc (k, r) est un arc strictement fort.

7. Aller à l’étape (2). Choisir un autre arc dans A(p) et continuer.


merci pour votre aide