Jalur Terpendek
Pelajaran 12 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.
Berapa jumlah sisi minimum yang diperlukan untuk mencapai end dari start? Dalam graf tanpa bobot (setiap sisi memiliki biaya yang sama), jawabannya persis seperti yang dihitung oleh BFS. Karena BFS mengunjungi simpul berdasarkan jarak yang semakin jauh dari titik awal, pertama kali kita mencapai end berarti kita menempuh jalur terpendek.
Caranya adalah memasukkan setiap simpul ke antrean bersama jaraknya sejauh ini. Mulai dengan (start, 0). Setiap kali kamu menemukan tetangga baru v dari simpul yang berjarak d, masukkan (v, d + 1) ke antrean. Saat v == end, kembalikan d + 1.
Ada dua kasus khusus. Jika start == end, jawabannya adalah 0. Jika BFS selesai tanpa pernah mencapai end, keduanya berada di komponen terhubung yang berbeda, dan jawabannya adalah -1.
Tantangan
MudahTulis fungsi shortestPath yang menerima array int 2D adjacency, int start, dan int end, lalu mengembalikan jarak terpendek (jumlah edge) dari start ke end.
- Jika
start == end, kembalikan0. - Jika
endtidak dapat dicapai daristart, kembalikan-1. - Jika tidak, kembalikan jumlah minimum edge di antara keduanya.
Kamu harus menggunakan class Graph (disediakan di graph), jangan gunakan fitur bawaan bahasa (map, set) untuk merepresentasikan adjacency. Data pendukung untuk algoritma (set yang menyimpan simpul yang telah dikunjungi, antrean) boleh menggunakan tipe dari pustaka standar.
Coba sendiri
#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;
}
Semua pelajaran di Graf, Seri Struktur Data #9
Latihan sendiri: Compiler C online