Thuật Toán BFS Tìm đường đi Qua ít đỉnh Trung Gian Nhất (Tìm Kiếm ...

Mời các bạn Download code tại: Click here

1. File Input:Click here

- Dòng đầu tiên gồm 3 số n, s, t tương ứng là số đỉnh, đỉnh bắt đầu và đỉnh kết thúc để tìm đường đi qua ít đỉnh trung gian nhất từ s tới t.

- n dòng tiếp theo, mỗi dòng gồm n số là ma trận trọng số của đồ thị, trong đó quy ước g[i, j] = 0 nếu không có đường đi trực tiếp từ i tới j.

2. File Output

- Ghi ra đường đi qua ít đỉnh trung gian nhất từ s tới t. (Ghi ra -1 nếu không tồn tại đường đi từ s tới t)

const fi = 'CHIEURONG.INP'; fo = 'CHIEURONG.OUT'; MAXN = 10000; var n, s, t: integer; g: array [1..MAXN, 1..MAXN] of integer; cx: array [1..MAXN] of boolean; Truoc: array [1..MAXN] of integer; Q: array [1..MAXN] of integer; Qf, Ql: integer; f: text; procedure Nhap; var i, j: integer; begin assign(f, fi); reset(f); readln(f, n, s, t); for i:= 1 to n do begin for j:= 1 to n do read(f, g[i, j]); readln(f); end; close(f); end; procedure Init; begin fillchar(cx, sizeof(cx), true); Qf:= 1; Ql:= 0; end; procedure Push(i: integer); begin inc(Ql); Q[Ql]:= i; end; function Pop: integer; begin Pop:= Q[Qf]; inc(Qf); end; function Empty: boolean; begin exit(Qf > Ql); end; procedure BFS; var u, v: integer; begin Push(s); cx[s]:= false; Truoc[s]:= -1; repeat u:= Pop; for v:= 1 to n do if cx[v] then if g[u, v] = 1 then begin Push(v); cx[v]:= false; Truoc[v]:= u; if v = t then exit; end; until Empty; end; procedure Duyet(i: integer); begin if Truoc[i] = -1 then write(f, i) else begin Duyet(Truoc[i]); write(f, ' -> ', i); end; end; procedure InKQ; begin if cx[t] = true then writeln(f, -1) else Duyet(t); writeln(f); end; BEGIN Nhap; Init; BFS; assign(f, fo); rewrite(f); InKQ; close(f); END.