Здравствуйте. Есть такая проблема. Дана задача, где надо реализовать алг. Дейкстры(кратчайшее раст. от одной до всех вершин) для графов. Алг. я знаю, но нужна матрица смежностей, которой нет в условии. пример: 5 3 1 (5 — n вершин 3-число краев(не знаю зачем) 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
26.10.2005 16:45
Цитата(Van @ 26.10.2005 11:37)
по-моему данных просто мало.
По моему, тоже... У тебя 5 вершин, и только 2 (или 3) связи между ними?
Данных явно недостаточно. Как только будут ВСЕ связи между вершинами, можно будет составить матрицу смежности...
С ней запросто справляется алгоритм Дейкстры который по ссылке... вот и все.
p.s. правда конткретный граф глупый, смысла искать кратчайшие пути нет...
Guest
10.11.2005 16:23
Спасибо всем тем, кто ответил мне, каждое ваше слово наводило на меня правильные мысли. Алгоритм Дейкстры я реализовал ещё 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.