Recherche du chemin le plus court dans un graphe à l’aide de classes

PHP Hard classes

Tâche «Recherche du chemin le plus court dans un graphe à l’aide de classes»

Implémentez la classe Graph pour représenter un graphe orienté pondéré. La classe doit contenir les méthodes addEdge(int $from, int $to, int $weight) pour ajouter une arête et shortestPath(int $start, int $end) pour trouver le chemin le plus court du sommet $start au sommet $end à l’aide de l’algorithme de Dijkstra. Si le chemin n’existe pas, la méthode doit retourner -1. Il est garanti que les poids des arêtes sont positifs, que le nombre de sommets ne dépasse pas 1000 et que le nombre d’arêtes est au maximum de 10000.

Format d\ entrée

Sur la première ligne, N (nombre de sommets) et M (nombre d’arêtes) sont donnés séparés par un espace. Sur les M lignes suivantes, les arêtes sont données sous la forme : from to weight. Sur la dernière ligne, start et end sont donnés.

Format de sortie

Un entier — le coût minimal du chemin de start à end, ou -1 si le chemin n’existe pas.

Exemples

Exemple 1

ENTRÉE

10

SORTIE

87

Exemple 2

ENTRÉE

SORTIE

15

Exemple 3

ENTRÉE

1

SORTIE

0

Exemple 4

ENTRÉE

1
2 7
1

SORTIE

-1

main.php