IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Востановление пути в Дейкстре...
сообщение
Сообщение #1


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Лень было переписывать алгоритм Дейкстры поэтому взял его для своей программы, но у меня массивы с 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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

Где-то ты намудрил, видимо ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Ищущий истину
******

Группа: Пользователи
Сообщений: 4 825
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


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


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 22:35
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name