Re: Добро пожаловать в лист "Решаем задачи по программированию - вместе"
Алгоритм Дейкстры:
для i от 1 до N выполнять
нц
предок[i]:=нач;
флаг[i]:=0;
D[i]:=C[нач,i]
кц
флаг[нач]:=1; {пока мы знаем только расстояние}
предок[нач]:=0 {от вершины нач до нее же, равное 0}
для i от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для j от 1 до N выполнять
если (флаг[j]=0 и (минрас > D[j]) {находим минимальное}
то минрас:=D[j]; {расстояние}
k:=j; {до непомеченных вершин}
все
флаг[k]:=1; {вершина k помечается просмотренной}
для j от 1 до N выполнять {выполняем просмотр}
если флаг[j]=0 и D[j]>D[k]+C[k,j]
{Т.е. если для вершины j еще не найдено кратчайшее расстояние
от нач, и из вершины k по дуге C[k,j] путь в j короче,
чем найденный ранее}
то D[j]:=D[k]+C[k,j] {то запоминаем его}
предок[j]:=k;
все
кц
-*Информационный канал Subscribe.Ru
Написать в лист: mailto:comp.soft.prog.vmeste-list@subscribe.ru
Отписаться: http://subscribe.ru/member/unsub?grp=comp.soft.prog.vmeste&email=
http://subscribe.ru/ mailto:ask@subscribe.ru
Hello Мичурина,
Friday, December 5, 2003, 11:40:54 PM, you wrote:
Дорогая Ирина, я конечно разобрал предложеный тобою алгоритм, но у
меня большая просьба: если сможеш подскажи как будет выглядить
структура записи. Вот какую предлагаю я:
указ=^имя1;
имя1=запись
предок:указ;
флаг:число;
D:число;
кон;
имя2=масив с имя1;
заранее благодарен.