Графы Опции

[Van]

Здравствуйте. Есть такая проблема. Дана задача, где надо реализовать
алг. Дейкстры(кратчайшее раст. от одной до всех вершин) для графов.
Алг. я знаю, но нужна матрица смежностей, которой нет в условии.
пример:
5 3 1 (5 — n вершин 3-число краев(не знаю зачем) 1-стартовая вершина))

1 2 5 (1 соединена с 2 5-весс ребра)
1 3 7 (1 соединена с 3 7-весс ребра)
3 4 10(---)
Ответ: 0 5 7 17 -1

Есть ли алгоритм где не нужна мат. см.? или

Как составить её по этим данным?
5 3 1
1 2 5
1 3 7
…….. Это не совсем мат. см.( по моему мнению)

а вот это, да
0 1 6 3
3 0 5 3
5 6 0 4
1 6 8 0

Если заполнять по первому примеру то ->
0 5 7 0 0
0 0 0 0 0
0 0 0 10 0
0 0 0 0 0
0 0 0 0 0
(я так делал, на выходе одни нули т.к мат. плохо заполнена)
Так вот эту ерунду надо достроить до нормальной
матрицы, с реальными данными.

Но вот как? по-моему данных просто мало.

Или надо реализовать хитрый проход по матрице?
0 5 7 17 -1
0 0 0 0 0
0 0 0 10 0
0 0 0 0 0
0 0 0 0 0 а потом по a[1, j] выводить? Но тогда зачем алг. Дейкстры?
помогите пожалуйста.

[volvo]

по-моему данных просто мало.

По моему, тоже... У тебя 5 вершин, и только 2 (или 3) связи между ними?

Данных явно недостаточно. Как только будут ВСЕ связи между вершинами, можно будет составить матрицу смежности...

[Altair]

http://forum.pascal.net.ru/index.php?showt...indpost&p=42335
Это алгоритм.
для твоего графа:

5 3 1
1 2 5
1 3 7
3 4 10

Матрица смежности имеет вид:


С ней запросто справляется алгоритм Дейкстры который по ссылке... вот и все.

p.s. правда конткретный граф глупый, смысла искать кратчайшие пути нет...

[Guest]

Спасибо всем тем, кто ответил мне, каждое ваше слово наводило на меня правильные мысли. Алгоритм Дейкстры я реализовал ещё 2 надели назад, пришлось спросить у препода одно, реализовать чуток другое, в общем главная ошибка - я для решения делал матрицу симметричной ->

0 1 2 3
1 0
2 0
3

for  I := 1 to levChis do
  m[j, I]  := m[I, j];

А надо было просто тупо её заполнять ->

Read(f1, n, levChis, start);    { levChis  - число граней    start - стартовая вершина}
For I  := 1 to levChis do
  Begin
    Read(f1, x, y, z);
    M[x, y] := z;
End;

Т.е граф был ориентированный. Вот после этого у меня всё правильно сработало (см. ниже) .

А теперь мне надо реализовать алг. BFS(Breadth-first-search (поиск в ширину)),
И ещё Флойда.
Подскажите пожалуйста где мне найти инфу по этому, да и вообще по графам.
А то у меня материала очень мало.

(Компилил на Дельфи)

program Deijckstra;
{$APPTYPE CONSOLE}
type
  Vertex = record
    otmetka:boolean;
    distFromStart:longInt;
  end;

var
  f1, f2:text;
  m:array [1..1000+1, 1..1000+1] of longInt; {mat smezh}
  i, j, x, y, z:integer;
  start:integer;
  v:array [1..2000] of Vertex;
  n, levChis, Vi:integer;
  otmecheno:integer;
  minDist:longInt;

procedure work;
begin
  for i := 1 to n do
    begin
      V[i].otmetka := false;
      v[i].distFromStart := M[start, i];
    end;

  v[start].otmetka := true;
  otmecheno := n - 1;

  while otmecheno <> 0 do
    begin
      minDist := maxInt;
      for i := 1 to n do
        if not v[i].otmetka and (v[i].distFromStart < minDist) then
          begin
            vI := i;
            minDist := v[i].distFromStart;
          end;

      v[Vi].otmetka := true;
      dec(otmecheno);

      for i := 1 to n do
         { if not V[i].otmetka then}
          if V[i].distFromStart > V[Vi].distFromStart + m[vI, i] then
              V[i].distFromStart := V[Vi].distFromStart + m[vI, i];
    end;{//while}
end; {//work}

begin
  assign(f1, 'input.txt');
  assign(f2, 'output.txt');
  reset(f1);
  rewrite(f2);

  read(f1, n, levChis, start);
  for i := 1 to levChis do
     begin
       read(f1, x, y, z);
       m[x, y] := z;
     end;

  for i := 1 to n do  {}
   for j := 1 to n do
     if (m[i, j] = 0) and (i <> j) then m[i, j] := 99999999;

  work;

  for i := 1 to n do
    begin
      if v[i].distFromStart = 99999999 then v[i].distFromStart := -1;
      write(f2, v[i].distFromStart, ' ');
    end;
  close(f1);
  close(f2);
end.

Сообщение отредактировано: volvo - 7.11.2006 23:46

[Altair]

Издиваешься?
ГРАФЫ
Поиск в ширину
Флойд