Кратчайший путь в графе Опции

[SeregaR1Val]

Помогите пожалуйста с программкой:
"Поиск кратчайшего пути в графе методом полного перебора в ширину с использованием АТД очередь"
Сам алгоритм у меня есть, но ничего не знаю про АТД очередь, ни у кого нет примеров такой программы?

[volvo]

работать с очередями, стеками и деками целый семестр, поэтому хотелось бы поподробнее.

Что именно "поподробнее"? Ты ж сказал, что у тебя есть алгоритм, но ты не знаешь про очереди. Все, что тебе надо знать - это то, что есть операции Put и Get, все остальное - уже детали реализации (на то он и абстрактный тип данных).

Мне дан такой алгоритм:

Не-не... Ты перепутал все на свете... Это не процедура называется Quepush... Вот так выглядит программа в простейшем случае:

uses queue_oop;

const
  N = 6;
  M: array[1 .. N, 1 .. N] of integer = (
    (0, 2, 0, 8, 0, 0),
    (0, 0, 3, 0, 7, 0),
    (0, 0, 0, 0, 1, 0),
    (0, 0, 0, 0, 6, 0),
    (0, 0, 0, 0, 0, 4),
    (0, 0, 0, 0, 0, 0)
  );

type
  WayType = array[1 .. N] of integer;

function visited(what: integer; path: WayType): boolean;
var i: integer;
begin
  visited := true;
  for i := low(path) to high(path) do
    if path[i] = what then exit;
  visited := false;
end;

var
  q: TQueue;
  i, j, start, finish, current: integer;
  finished: boolean;
  Way: WayType;

begin
  q.init;

  start := 1; finish := 5;

  q.put(start);
  While not q.isEmpty do begin
    Current := q.get;
    Finished := Current = finish;
    j:=1;
    while j<=N do begin
      if (M[Current,j] <> 0) and not visited(j, way) then begin
        Way[j] := Current;
  	Finished:=(j = finish);
        // если не закончили перебор - добавляем очередную вершину
	// в очередь, чтобы потом к ней вернуться...
        if not Finished then q.put(j)
      end;
      inc(j);
    end;
  end;

  // а когда закончили - то печатаем путь
  // от конечной вершины к начальной
  i:=finish;
  write(i:3);

  while i<>start do begin
    write(Way[i]:3);
    i:=Way[i];
  end;
  writeln;

end.

(я использовал собственный модуль queue_oop, в принципе можешь использовать любой другой, по названиям методов понятно, что они делают: Put - забрасывает элемент в конец очереди, Get - вытаскивает элемент из ее начала)

Сообщение отредактировано: volvo - 2.10.2008 19:31