|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rodion Gorkovenko 2:5030/1286.6 05 Jun 2003 15:15:00
To : Alex Rinas
Subject : Алгоритм Дейкстры
--------------------------------------------------------------------------------
03 Jun 03 08:11, you wrote to All:
AR> Срочно нужна помошь в решении задачи по графам: Определение
AR> кратчайшего маршрута движения автомобиля (>=7 вершин >=10 дуг) указанным
AR> алгоритмом на турбо-паскале.
Я сразу оговорюсь - я в этом не разбираюсь совершенно, алгоритм Дейкстры уже
забыл и на паскале писать не умею... Тем не менее, решил поднапрячься и вот, что
у меня получилось. Точнее что получилось - смотри после подписи, а пока попробую
объяснить.
В целом алгоритм Дейстры - штука нехитрая. Его целью является поиск кратчайших
путей из заданной вершины во все остальные (я так понимаю, это называется
построением дерева кратчайших путей - а сам алгоритм это вариант поиска в ширину
- правильно?) Идея в общем простая, как детский лепет.
Пусть дан граф с N вершинами.
Во-первых мы заводим массив размером N, в котором будем записывать текущие длины
путей до соответствующих вершин.
Пока что мы не нашли ни одного пути (путя?) и все эти длины равны, скажем,
бесконечности (или, скажем, вообще не определены - неважно). Однако, подумав, мы
можем догадаться, что путь в одну из вершин мы знаем точно - в ту вершину,
откуда нужно начинать. Этот путь состоит ровным счетом из ничего и его длина
равна 0.
Все вершины кроме того удобно разбить на три группы
1) те, до которых кратчайший путь уже найден
2) те, до которых найден хоть какой-то путь
3) те, до которых путь пока не найден
Для обозначения принадлежности вершин к той или иной группе мы заведем еще
массив флагов, имеющих три соответствующих состояния.
Сначала все вершины, кроме стартовой, нужно будет отнести, разумеется, к третьей
группе. Стартовую хорошо бы отнести к первой, но для инициализации алгоритма нам
удобнее засунуть ее во вторую, сделав вид, что мы еще точно не знаем, кратчайший
ли это путь. (который состоит из ничего и равен по длине 0)
Теперь мы начинаем делать могучие шаги (итерации).
Hа каждом шаге мы сначала просматриваем все вершины, которые находятся во 2
группе (поэтому мы и засобачили сюда стартовую вершину) - вершины 1 группы нас
уже не интересуют, а с вершинами 3 группы мы пока ничего не можем сделать. Из
вершин второй группы мы выбираем ту, длина пути до которой минимальна. При этом
мы помним, что все пути из вершин 1 группы мы уже опробовали (см. дальше), а
пути в остальные вершины 2 и 3 групп будут длиннее, чем теперешний путь до этой
минимальной. Поэтому мы можем быть твердо уверены, что к ней мы на этом шаге
нашли кратчайший путь.
Осталось понять, как же мы строим эти зловонные пути - пока про это ничего
сказано не было. Строительство путей происходит на каждом шаге, после
определения минимальной вершины. Мы просматриваем все вершины 2 и 3 группы, в
которые есть ребро (дуга) из этой минимальной, то есть куда мы можем добраться
следующим ходом. Если какая-то из этих вершин принадлежит 3 группе, мы радостно
осознаем, что мы нашли до нее путь (через текущую, минимальную вершину) и
поэтому ее можно перевести во вторую группу. В таком случае мы переводим ее во
вторую группу, а в массиве длин путей записываем, что добрались мы до нее по
пути, состоящему из пути до текущей минимальной вершины (эту длину мы берем в
этом же массиве) и ребра, соединяющего минимальную вершину с ней.
Если же рассматриваемая вершина принадлежит ко 2 группе, значит мы уже находили
какой-то путь к ней (его длина уже записана в массиве длин) - и нам нужно
определить, короче ли новый путь (из текущей минимальной вершины) чем старый
(длина которого записана в массиве). Если он короче, то мы поступаем так же, как
если бы эта вершина принадлежала к 3 группе.
Вот, таким образом мы добавили еще одну вершину к 1 группе, и можем начинать
следующий шаг алгоритма. Когда при поиске минимальной вершины будет выяснено,
что все вершины находятся в 1 группе, работу можно считать законченной.
В этом замечательном алгоритме (который я косноязычно описал) непонятно только
одно - длины кратчайших путей мы получили - а как нам теперь восстановить сами
пути - то есть порядок прохождения вершин на пути к конкретной какой-нибудь.
Чтобы это можно было определить, нам изначально нужен еще один массив по
количеству вершин (N), в котором мы будем хранить информацию о том, из какой
вершины мы добрались в данную. Запись в этот массив производится тогда же, когда
и запись в массив длин - мы записываем новую длину в один массив, а номер
вершины, из которой мы добрались в текущую по пути с указанной длиной, в другой.
Поскольку по ходу алгоритма значения из этого массива не используются, я его не
упомянул сразу, чтобы было проще (вот уж не знаю, стало ли действительно проще
или нет).
Реализация данного алгоритма вон там, после подписи. Программа запускается
примерно так:
DIJKSTRA.EXE <input.txt> <output.txt>
Я привожу файл DIJKSTRA.PAS, из которого при компиляции должна бы получиться эта
программа а также пример входного файла DIJKSTRA.TXT, который имеет следующий
формат:
N {количество вершин}
S {номер стартовой вершины}
From1 To1 Weight1 {тройка чисел, обозначающих ребра - из какой вершины оно}
{выходит, в которую приходит и его вес - то есть его длина или там, сколько}
{штрафов по проезду по нему придется заплатить}
From2 To2 Weight2
From3 To3 Weight3
.... {и так далее}
Прошу пардона, что так криво объяснил - у меня тут батарейка села в будильнике,
нужно идти покупать... Hу и еще масса причин, включая мою собственную кривость
;)
Писал сам, только что (пятый паскаль достал ;) - работало, хотя глюки не
исключены - самое тяжелое, если алгоритмические ;(
с почтеньем,
Rodion
=== Cut ===пошел файл DIJKSTRA.PAS
{This text could be used anywhere in any possible or impossible way}
{without any agreements or permissions from whoever could it be}
{I am new to programming itself, to pascal and I do not know anything}
{about of Dijkstra's algotirhms and any other, so you should use this}
{text on your own risk and I am not in response to results of using it,}
{regardless, which way of using it you kept}
{Commetns, complains and curses of any kind could be addressed to anyone,}
{including fidonet 2:5030/1286.6}
{Excuse me for poor english - I forgot about installing keyrus this morning}
{$A-,B-,D+,E-,F-,I+,L+,N+,O-,R-,S+,V-}
{$M 16384,0,655360}
program dijkstra;
const
MAX_VERTICES=128;{sqr(MAX_VERTICES)*sizeof(int) should be less than 32K}
STATE_EVALUATED=0;{shortest path to this vertex is already found}
STATE_PROCESSING=1;{some path to this vertex is already found}
STATE_UNTOUCHED=2;{no path to this vertex is found yet}
NO_VERTEX=-1;
NO_EDGE=-1;
type
intVector=array[0..0] of integer;
pInteger=^intVector;
vertexInfo=record
pathFrom:integer;
currentPathLength:integer;
currentState:integer;
end;{vertexInfo}
vertexInfoVector=array [0..0] of vertexInfo;
var
nVertices,matrixSize,startVertex:integer;
matrix:^intVector;
verticesInfo:^vertexInfoVector;
function
GetMatrix(vertexFrom,vertexTo:integer):integer;
begin
GetMatrix:=matrix^[vertexFrom*nVertices+vertexTo];
end;{GetMatrix}
procedure
SetMatrix(vertexFrom,vertexTo,edgeWeight:integer);
begin
matrix^[vertexFrom*nVertices+vertexTo]:=edgeWeight;
end;{SetMatrix}
function
Initialize:boolean;
var
inFile:text;
i,vertexFrom,vertexTo,edgeWeight:integer;
begin
Initialize:=FALSE;
if ParamCount<2 then
Exit;
{$I-}
Assign(inFile,ParamStr(1));
Reset(inFile);
if IOresult<>0 then
Exit;
Read(inFile,nVertices,startVertex);
if (IOresult<>0) or (nVertices<0) or (nVertices>=MAX_VERTICES) then
Exit;
matrixSize:=nVertices*nVertices*sizeof(integer);
GetMem(matrix,matrixSize);
for i:=(matrixSize div sizeof(integer))-1 downto 0 do
matrix^[i]:=NO_EDGE;
while not SeekEOF(inFile) do begin
Read(inFile,vertexFrom,vertexTo,edgeWeight);
if IOresult<>0 then
Exit;
SetMatrix(vertexFrom,vertexTo,edgeWeight);
end;{while}
close(inFile);
{$I+}
GetMem(verticesInfo,nVertices*sizeof(vertexInfo));
for i:=nVertices-1 downto 0 do
verticesInfo^[i].currentState:=STATE_UNTOUCHED;
verticesInfo^[startVertex].currentState:=STATE_PROCESSING;
verticesInfo^[startVertex].currentPathLength:=0;
verticesInfo^[startVertex].pathFrom:=NO_VERTEX;
Initialize:=TRUE;
end;{Initialize}
procedure
DestroyAll;
begin
FreeMem(verticesInfo,nVertices*sizeof(vertexInfo));
FreeMem(matrix,matrixSize);
end;{DestroyAll}
procedure
Process;
label
newIteration,doneProcessing;
var
bestLength,bestVertex,currentLength,currentVertex:integer;
begin
{On each iteration shortest path to some particular vertex is found}
newIteration:
{Searching for vertex from set of vertices currently being processed,}
{path to which is shortest for this time}
bestVertex:=-1;
for currentVertex:=nVertices-1 downto 0 do begin
if verticesInfo^[currentVertex].currentState=STATE_PROCESSING then begin
currentLength:=verticesInfo^[currentVertex].currentPathLength;
if (bestVertex<0) or (currentLength<bestLength) then begin
bestVertex:=currentVertex;
bestLength:=currentLength;
end;{if}
end;{if}
end;{for}
{If nothing found, shortest paths to all vertices is evaluated already}
if bestVertex<0 then
goto doneProcessing;
{If some vertex was found, current path to it is the shortest one}
verticesInfo^[bestVertex].currentState:=STATE_EVALUATED;
{Evaluating path lengths to vertices, which are connected to this}
for currentVertex:=nVertices-1 downto 0 do begin
currentLength:=GetMatrix(bestVertex,currentVertex);
if (verticesInfo^[currentVertex].currentState<>STATE_EVALUATED) and
(currentLength<>NO_EDGE) then begin
currentLength:=currentLength+bestLength;
if (verticesInfo^[currentVertex].currentPathLength>currentLength) or
(verticesInfo^[currentVertex].currentState=STATE_UNTOUCHED) then begin
verticesInfo^[currentVertex].currentState:=STATE_PROCESSING;
verticesInfo^[currentVertex].currentPathLength:=currentLength;
verticesInfo^[currentVertex].pathFrom:=bestVertex;
end;{if}
end;{if}
end;{for}
goto newIteration;
doneProcessing:
end;{Process}
procedure
WriteResults;
var
outFile:text;
i,currentVertex,currentLength,currentDepth:integer;
doWrite:boolean;
begin
{$I-}
Assign(outFile,ParamStr(2));
Rewrite(outFile);
if IOresult<>0 then
Exit;
{$I+}
currentVertex:=startVertex;
currentDepth:=0;
doWrite:=TRUE;
repeat
if doWrite then begin
for i:=0 to currentDepth do
write(outFile,' ');
currentLength:=verticesInfo^[currentVertex].currentPathLength;
writeln(outFile,'Vertex-',currentVertex,' by ',currentLength);
doWrite:=FALSE;
end;{if}
i:=nVertices-1;
while i>=0 do begin
if verticesInfo^[i].pathFrom=currentVertex then begin
currentVertex:=i;
i:=-2;{Signal of special loop break condition}
{if nothing found i would be equal to -1}
currentDepth:=currentDepth+1;
doWrite:=TRUE;
end;{if}
i:=i-1;
end;{while}
if i=-1 then begin
i:=verticesInfo^[currentVertex].pathFrom;
verticesInfo^[currentVertex].pathFrom:=NO_VERTEX;
currentVertex:=i;
currentDepth:=currentDepth-1;
end;{if}
until currentDepth<0;
close(outFile);
end;{WriteResults}
begin
if not Initialize then
Halt(1);
Process;
WriteResults;
DestroyAll;
end.{main part}
=== Cut ===пошел файл DIJKSTRA.TXT
6
2
0 4 1
1 3 2
1 5 1
2 0 10
2 1 5
2 3 8
3 4 4
4 1 9
4 3 1
5 3 1
5 4 6
===========все, больше ничего нет
---
* Origin: (2:5030/1286.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Алгоритм Дейкстры