Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Дейкстра / 20 сообщений из 20, страница 1 из 1
14.07.2004, 07:12
    #32602896
Югг
Югг
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Помогите пожалуйста разобраться или подскажите ссылку где это более ли менее хорошо написано. А то чего-то я не допонимаю.

Как я поняла у меня есть допустим 5 пунктов. Я составляю матрицу расстояний между ними.

Код: plaintext
1.
2.
3.
4.
5.
Rast[ 5 ][ 5 ] = { 0   2   4   5   6 
                    2   0   7   9   1   
                    4   7   0   8   3 
                    5   9   8   0   4 
                    6   1   3   4   0 }
Правильно?

А вот само описание алгоритма я не совсем понимаю. Может у кого-нибудь есть пример?
Спасибо заранее
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 08:19
    #32602931
ScareCrow
ScareCrow
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
http://program.rin.ru/cgi-bin/print.pl?id=686
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 12:43
    #32603594
Timm
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Есть очень хорошая книжка по алгоритмам на графах.
Называется "Дискретная оптимизация", авторы Асанов, Баранский, Расин.
В ней очень хорошо все описано.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 14:24
    #32603913
Yet another cat
Yet another cat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Угу. Ты еще найди где-нибудь эту книгу. У нее тираж был прямо скажем небольшой.
=====
Cat и его покойный друг Chicago
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 14:34
    #32603963
Югг
Югг
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Народ а может у кого-нить есть реализация на С++ для неориентированного!
а то срочно человеку надо, а я не могу нигде найти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 14:50
    #32604028
Timm
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Yet another catУгу. Ты еще найди где-нибудь эту книгу. У нее тираж был прямо скажем небольшой.
=====
Cat и его покойный друг Chicago
Да, действительно, тираж у нее - капля в море, но у меня есть )))
Более того, я слушал этот курс у автора учебника...
И совсем по секрету: эта книга (вполне возможно) есть у меня в pdf-е, только надо искать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 15:02
    #32604063
Timm
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Алгоритм дейкстры на С
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 15:03
    #32604064
Югг
Югг
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Раз не у кого нет реализации, объясните мне на пальцах или исправьте ошибки в реализации, а то она не работает, а человеку срочно надо, а мне что бы найти ошибку надо сначала разобраться с методом.
Может кто быстро сообразит. Пожалуйста!!!!

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
#include <conio.h>
#include <stdio.h>
#include <values.h>
#include <stdlib.h>
#include <math.h>
#include <iostream.h>
 main()
{
 clrscr();
 int q,t;
 int z,i,j;
 int k,min,xx;
  int const n= 6 ;
float a[n][n] = {
	     { 1000 ,    2 ,    4 , 1000 , 1000 ,    3 },
	     {    2 , 1000 , 1000 ,    7 , 1000 , 1000 },
	     {    4 , 1000 , 1000 ,    6 , 1000 , 1000 },
	     { 1000 ,    7 ,    6 , 1000 ,    1 , 1000 },
	     { 1000 , 1000 , 1000 ,    1 , 1000 , 1000 },
	     {    3 , 1000 , 1000 , 1000 ,    1 , 1000 }};

  printf("First: \n");
  scanf("%d", q );
  printf("End: \n");
  scanf("%d", t );
  printf("\n");
  // -----------------------------------------------------------------------
 
  int *P_M=new int[n];
  int *V_M=new int[n];
  P_M[q- 1 ]= 0 ;

   for (i= 1 ;i<n;i++)
    {
     if(i!=q) V_M[i]= 1000 ;
    }
   z = q;
   while(z!=t)
       {   k= 0 ;
	   for (i= 1 ;i<n;i++)
	    {
                   { if (V_M[i] > V_M[z]+a[z][i])
			  { V_M[i] = V_M[z]+a[z][i];
    	                              k++;
		              }
		  }
	   }
	    //printf("%d", k);

	    //printf("\n");

	   //cout << k << "\n";
        }
 while (k!= 0 );
       min =  1000 ;
       xx= 0 ;
    for (i= 1 ;i<n;i++)
  {
    if((V_M[i]= 1000 )&&(min >= V_M[i]) && (P_M[i]!=V_M[i]))
      { min=V_M[i];
	xx=i;}
  }
  z=xx;
  V_M[xx]= 1 ;//min;
 // z=xx;
  P_M[xx]=V_M[xx];

}
   z=t;
   cout <<" Кратчайший путь: \n"<< t << " ";
  while (t!=q)
  {
    for(i= 0 ;i<n;i++)
     { if(P_M[j]=P_M[i]+a[i][j])// (P_M[z]-P_M[i]==a[z][i])
	  { z=i;
	    //cout << j <<" ";
	    printf("%d", i);
	  }

	 }
  }
delete [] a;
delete [] V_M;
delete []P_M;

getch();
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 15:03
    #32604067
Timm
Timm
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Упс, очепятка вышла, Дейкстры конечно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 15:04
    #32604075
Югг
Югг
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Раз не у кого нет реализации, объясните мне на пальцах или исправьте ошибки в реализации, а то она не работает, а человеку срочно надо, а мне что бы найти ошибку надо сначала разобраться с методом.
Может кто быстро сообразит. Пожалуйста!!!!

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
#include <conio.h>
#include <stdio.h>
#include <values.h>
#include <stdlib.h>
#include <math.h>
#include <iostream.h>
 main()
{
 clrscr();
 int q,t;
 int z,i,j;
 int k,min,xx;
  int const n= 6 ;
float a[n][n] = {
	     { 1000 ,    2 ,    4 , 1000 , 1000 ,    3 },
	     {    2 , 1000 , 1000 ,    7 , 1000 , 1000 },
	     {    4 , 1000 , 1000 ,    6 , 1000 , 1000 },
	     { 1000 ,    7 ,    6 , 1000 ,    1 , 1000 },
	     { 1000 , 1000 , 1000 ,    1 , 1000 , 1000 },
	     {    3 , 1000 , 1000 , 1000 ,    1 , 1000 }};

  printf("First: \n");
  scanf("%d", q );
  printf("End: \n");
  scanf("%d", t );
  printf("\n");
  // -----------------------------------------------------------------------
 
  int *P_M=new int[n];
  int *V_M=new int[n];
  P_M[q- 1 ]= 0 ;

   for (i= 1 ;i<n;i++)
    {
     if(i!=q) V_M[i]= 1000 ;
    }
   z = q;
   while(z!=t)
       {   k= 0 ;
	   for (i= 1 ;i<n;i++)
	    {
                   { if (V_M[i] > V_M[z]+a[z][i])
			  { V_M[i] = V_M[z]+a[z][i];
    	                              k++;
		              }
		  }
	   }
	    //printf("%d", k);

	    //printf("\n");

	   //cout << k << "\n";
        }
 while (k!= 0 );
       min =  1000 ;
       xx= 0 ;
    for (i= 1 ;i<n;i++)
  {
    if((V_M[i]= 1000 )&&(min >= V_M[i]) && (P_M[i]!=V_M[i]))
      { min=V_M[i];
	xx=i;}
  }
  z=xx;
  V_M[xx]= 1 ;//min;
 // z=xx;
  P_M[xx]=V_M[xx];

}
   z=t;
   cout <<" Кратчайший путь: \n"<< t << " ";
  while (t!=q)
  {
    for(i= 0 ;i<n;i++)
     { if(P_M[j]=P_M[i]+a[i][j])// (P_M[z]-P_M[i]==a[z][i])
	  { z=i;
	    //cout << j <<" ";
	    printf("%d", i);
	  }

	 }
  }
delete [] a;
delete [] V_M;
delete []P_M;

getch();
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.07.2004, 15:50
    #32604210
JibSkeart
JibSkeart
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Никто тебе не поможет ...
мы же не телепаты , отуда нам знать , на что он ругается итд итп

 ш
(';')
(V),(V),,
Код: plaintext
 JS
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.07.2004, 05:09
    #32604996
Югг
Югг
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
А я уже сама разобралась. Пришлось правда часика два посидеть поразбираться с алгоритмом, но вроде усе номано. -)))
Так что всем спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.07.2004, 07:05
    #32607212
Yet another cat
Yet another cat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Timm Yet another catУгу. Ты еще найди где-нибудь эту книгу. У нее тираж был прямо скажем небольшой.
Да, действительно, тираж у нее - капля в море, но у меня есть )))
Более того, я слушал этот курс у автора учебника...
И совсем по секрету: эта книга (вполне возможно) есть у меня в pdf-е, только надо искать.

Дык и у меня есть (не в pdf). Потому что я слушал курс у одного автора учебника, учился в аспирантуре у другого, а теорию графов нам когда-то читал третий
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
28.09.2005, 11:36
    #33292677
e,ju
e,ju
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Кто-нибудь, помогите! Нужен алг. Дейкстра на Delphi.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.10.2005, 10:46
    #33300089
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
ЮггНарод а может у кого-нить есть реализация на С++ для неориентированного!
а то срочно человеку надо, а я не могу нигде найти.

Поищи в сети Graph template library. Она старовата была, но работала и Дейкстра там был точно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.10.2005, 14:02
    #33300171
DocAl
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Тема-то прошлогодняя... Свежачок-с)
Поднявшего её интересует реализация на дельфях.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
11.12.2006, 03:22
    #34188907
аываыа
аываыа
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
ммм...скиньте плз рабочий исходник...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.12.2006, 11:35
    #34189572
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
аываыаммм...скиньте плз рабочий исходник...

а выше, что , не рабочий?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.06.2007, 14:51
    #34591923
eXisTence
eXisTence
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
Народ, помогите кто исправить выше выложенный код на с++ алгоритма дейкстра, или киньте кто ссылку на рабочий исходник алгоритма дейкстра на с++ или билдор с++.
Срочно надо для написания курсача( Заранее спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2007, 09:52
    #34600904
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм Дейкстра
eXisTenceНарод, помогите кто исправить выше выложенный код на с++ алгоритма дейкстра, или киньте кто ссылку на рабочий исходник алгоритма дейкстра на с++ или билдор с++.
Срочно надо для написания курсача( Заранее спасибо.

100$

за то, что рассмешил, скидка 20%
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Дейкстра / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 504ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1345993]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 158ms
get topic data:
 13ms
get forum data:
 2ms
get page messages:
 68ms
get tp. blocked users:
 1ms
others: 233ms
total:  504ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]