Kürzester Pfad
Lektion 12 von 14 im Kurs Graphen - Datenstrukturen-Serie #9 von Coddy.
Wie wenige Kanten werden benötigt, um von start nach end zu gelangen? In einem ungewichteten Graphen (jede Kante hat die gleichen Kosten) ist die Antwort genau das, was BFS berechnet. Da BFS Knoten in zunehmender Entfernung vom Start besucht, ist das erste Mal, dass wir end erreichen, entlang eines kürzesten Pfades.
Der Trick besteht darin, jeden Knoten zusammen mit seiner bisherigen Entfernung in die Warteschlange zu stellen. Beginnen Sie mit (start, 0). Jedes Mal, wenn Sie einen neuen Nachbarn v von einem Knoten in der Entfernung d entdecken, stellen Sie (v, d + 1) in die Warteschlange. Wenn v == end, geben Sie d + 1 zurück.
Zwei Sonderfälle. Wenn start == end, ist die Antwort 0. Wenn BFS beendet wird, ohne jemals end zu erreichen, befinden sich die beiden in unterschiedlichen Zusammenhangskomponenten, und die Antwort ist -1.
Aufgabe
EinfachSchreiben Sie eine Funktion shortestPath, die ein 2D-Int-Array adjacency, einen Int-Wert start und einen Int-Wert end erhält und die kürzeste Distanz (Anzahl der Kanten) von start zu end zurückgibt.
- Wenn
start == end, geben Sie0zurück. - Wenn
endvonstartaus nicht erreichbar ist, geben Sie-1zurück. - Andernfalls geben Sie die minimale Anzahl an Kanten zwischen ihnen zurück.
Sie müssen die Klasse Graph verwenden (bereitgestellt in graph) - verwenden Sie keine in der Sprache eingebauten Typen (Maps, Sets), um die Adjazenz zu modellieren. Hilfsdaten für den Algorithmus (Visited-Sets, Queues) dürfen Standardbibliotheks-Typen verwenden.
Probier es selbst
#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;
}