Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Востановление пути в Дейкстре...

Автор: Altair 20.11.2006 2:13

Лень было переписывать http://forum.pascal.net.ru/index.php?s=&showtopic=4030&view=findpost&p=42335 поэтому взял его для своей программы, но у меня массивы с 0 начинаются. (java).
Тоже не хотелось переделывать под [1 .. *]

Вобщем вот что получилось:

public void dijkstra(int u1, int u2){

int n = this.IdCount;
double w[][] =this.weightMatrix;

path = new int[this.IdCount];
double weight=0;

// для расчетов
int i,k,j,t;
double gm,dd,min;
double d[] = new double [30];
double m[] = new double [30];
int p[] = new int [30];
gm=10000;
length=0;
if (u1!=u2) {
i=1;
do {
d[i-1]=gm;
p[i-1]=0;
m[i-1]=0;
i++;
} while ((i<=n));
d[u1-1]=0; t=u1;
while (length==0) {
i=1;
do {
if ( w[t-1][i-1] < gm) {
dd=d[t-1]+w[t-1][i-1];
if (d[i-1]>dd) { d[i-1]=dd; p[i-1]=t;}
}
i=i+1;
} while ((i<=n));
min=gm; i=1; k=0;
do {
if (m[i-1]==0) {
if (d[i-1]<min) { min=d[i-1]; k=i;}
}
i++;
} while ((i<=n));
if (k!=0) {
m[k-1]=1; t=k;
if (t==u2) { length=1;} //2
} else { length=-1;}
}
if (length==1) {
path[0]=u2; length=1; j=u2;
do {
path[length-1]=p[j-1]; j=p[j-1]; length++;
} while((j!=u1));
i=1; k=Math.round(length/2);
do {
t=path[i-1]; path[i-1]=path[length-i-1]; path[length-i-1]=t; i++;
} while((i<=k));
length--;
}
weight=d[u2-1];
}
System.out.println(weight);
}
public void showPath(){
for (int i=0; i<length; i++) {
((Nodes)nodes.get(this.path[i])).setPolColor(Color.cyan);
}
}



Длинну маршрута считает нормально!
НО! Почему то неверно сам маршрут получается!
Т.е. вот например:
Прикрепленное изображение


Длинна пути скидывается в консоль Java.

Вопрос такой - это у нас сам алгоритм в FAQ неверный или я где то ошибся когда его портировал под нулевые массивы?
У меня нет возможности сейчас проверить алгритм в FAQ... sad.gif

Автор: volvo 20.11.2006 2:37

Олег, программа из FAQ-а отработала прекрасно для приведенного там графа:

Цитата(Colsole)
u1 = 1
u2 = 20
w=26.00
path
1 - 2 - 6 - 12 - 13 - 15 - 18 - 20 -
Все совпадает с реальными значениями... (FPC 2.0.4)

Где-то ты намудрил, видимо ...

Автор: Altair 20.11.2006 7:12

Ок! Спасибо за проверку!
Исправил!
Перемудрил с индексами... все же пришлось переправить алгоритм более серьезно под массивы [0..n], а не выкручиваться добавлением или отниманием где нужно единицы.