Plus court chemin
Leçon 12 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Quel est le nombre minimum d'arêtes pour aller de start à end ? Dans un graphe non pondéré (chaque arête a un coût égal), la réponse est exactement ce que le BFS calcule. Parce que le BFS visite les sommets par distance croissante depuis le départ, la première fois que nous atteignons end, c'est via un chemin le plus court.
L'astuce consiste à enfiler chaque sommet avec sa distance actuelle. Commencez par (start, 0). Chaque fois que vous découvrez un nouveau voisin v à partir d'un sommet à la distance d, enfilez (v, d + 1). Quand v == end, retournez d + 1.
Deux cas particuliers. Si start == end, la réponse est 0. Si le BFS se termine sans jamais atteindre end, les deux se trouvent dans des composantes connexes différentes, et la réponse est -1.
Défi
FacileÉcrivez une fonction shortestPath qui reçoit un tableau d'entiers 2D adjacency, un entier start et un entier end, et renvoie la distance la plus courte (nombre d'arêtes) de start à end.
- Si
start == end, renvoyez0. - Si
endest inatteignable depuisstart, renvoyez-1. - Sinon, renvoyez le nombre minimum d'arêtes entre eux.
Vous devez utiliser la classe Graph (fournie dans graph) - n'utilisez pas les types intégrés du langage (maps, sets) pour modéliser l'adjacence. Les données auxiliaires pour l'algorithme (ensembles de sommets visités, files d'attente) peuvent utiliser les types de la bibliothèque standard (stdlib).
Essayez vous-même
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}