Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 24.06.2010, 21:07   #1
Maksik
Пользователь
 
Регистрация: 24.06.2009
Сообщений: 14
По умолчанию Все пути минимального веса (графы)

Используя алгоритм Дейкстры найти пути минимального веса для всех пар вершин. Граф состоит из N вершин, пронумерованных от 0 до N-1 соответственно. Граф задан матрицей весов.
Во входном файле нам даётся число - размер матрицы, следом матрица весов. В выходном файле надо вывести матрицу весов найденных путей.

test.in
5
0 1 0 10 0
1 0 1 0 0
0 1 0 1 1
10 0 1 0 8
0 0 1 8 0
test.out
0 1 2 3 3
1 0 1 2 2
2 1 0 1 1
3 2 1 0 2
3 2 1 2 0

Код:
program put;

const maxn=100;
inf=10000;

type matrix = array [1..maxn,1..maxn] of integer;

var D : array[1..MaxN] of integer; 
visited:array [1..maxn] of boolean;
tabl:matrix;
i,j,t,n:integer;
fi,fo:text;

procedure Deis (A : Matrix; N, s : integer); 
var i, j, v, min : longint;
begin
    visited[s] := TRUE; 
    for i := 1 to N do D[i] := A[s, i];
    for i := 1 to n-1 do 
    begin
        min := inf;
        for j := 1 to N do if (not visited[j]) and (D[j] < min) then
        begin
            min := D[j]; 
            v := j; 
        end;
        for j := 1 to N do if (D[j] > D[v] + A[v, j]) and (D[v] < inf) and (A[v, j] < inf)
        then D[j] := D[v] + A[v, j]; 
        s := v; 
        visited[v] := TRUE; 
    end;
end;

begin
assign(fi,'c:/test.in');
assign(fo,'c:/test.out');
reset(fi);
rewrite(fo);
readln(fi,n);
for i:=1 to n do
    begin
         for j:=1 to n do
             begin
             read(fi,tabl[i,j]);
             end;
    readln(fi);
    end;

for i:=1 to n do
    begin
    deis(tabl,n,i);
    for j:=1 to n do write(d[j]);
    writeln;
    end;
    
close(fi);
close(fo);
end.
Не могу сообразить, почему не считает? Выдаёт только то, что в входном файле.
Maksik вне форума Ответить с цитированием
Старый 24.06.2010, 21:24   #2
Maksik
Пользователь
 
Регистрация: 24.06.2009
Сообщений: 14
По умолчанию

Находил несколько версий алгоритма Дейсктры, почему-то несколько пробовал и все они плохо работают (сейчас в мою сторону посыпятся сообщения про мои крывые руки ). Выложите алгоритм Дейсктры. (в гугл не отправлять).
Maksik вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
графы - Все возможные пути manuk Помощь студентам 9 23.05.2010 23:58
Нахождение минимального пути по графам Nextgen Общие вопросы C/C++ 3 30.12.2009 14:14
ПОСЛЕДНЯЯ МОЯ ТЕМА НА ЭТОМ ФОРУМЕ. TurboPascal: теория графов, определить длину минимального пути методом ulala Помощь студентам 8 23.12.2009 18:55
Поиск минимального и максимального пути в графе!!!! OZZY_91 Помощь студентам 1 18.11.2009 13:20
уменьшить все элементы с четными индаксами на величину минимального элемента ginzor Помощь студентам 4 02.11.2009 15:26