ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Дейкстра
20 сообщений из 20, страница 1 из 1
Алгоритм Дейкстра
    #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, 07:12
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32602931
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
http://program.rin.ru/cgi-bin/print.pl?id=686
...
Рейтинг: 0 / 0
14.07.2004, 08:19
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32603594
Фотография Timm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Timm
Участник
Есть очень хорошая книжка по алгоритмам на графах.
Называется "Дискретная оптимизация", авторы Асанов, Баранский, Расин.
В ней очень хорошо все описано.
...
Рейтинг: 0 / 0
14.07.2004, 12:43
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32603913
Фотография Yet another cat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Yet another cat
Участник
Угу. Ты еще найди где-нибудь эту книгу. У нее тираж был прямо скажем небольшой.
=====
Cat и его покойный друг Chicago
...
Рейтинг: 0 / 0
14.07.2004, 14:24
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32603963
Югг
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Югг
Участник
Народ а может у кого-нить есть реализация на С++ для неориентированного!
а то срочно человеку надо, а я не могу нигде найти.
...
Рейтинг: 0 / 0
14.07.2004, 14:34
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32604028
Фотография Timm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Timm
Участник
Yet another catУгу. Ты еще найди где-нибудь эту книгу. У нее тираж был прямо скажем небольшой.
=====
Cat и его покойный друг Chicago
Да, действительно, тираж у нее - капля в море, но у меня есть )))
Более того, я слушал этот курс у автора учебника...
И совсем по секрету: эта книга (вполне возможно) есть у меня в pdf-е, только надо искать.
...
Рейтинг: 0 / 0
14.07.2004, 14:50
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32604063
Фотография Timm
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Timm
Участник
Алгоритм дейкстры на С
...
Рейтинг: 0 / 0
14.07.2004, 15:02
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #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:03
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #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:04
| Ответить | Цитировать | Написать  
Алгоритм Дейкстра
    #32604210
Фотография JibSkeart
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JibSkeart
Участник
Никто тебе не поможет ...
мы же не телепаты , отуда нам знать , на что он ругается итд итп

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

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

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

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

100$

за то, что рассмешил, скидка 20%
...
Рейтинг: 0 / 0
18.06.2007, 09:52
| Ответить | Цитировать | Написать  
20 сообщений из 20, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм Дейкстра
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=32604075&tid=1345993]:
 0ms
get settings:
 6ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 46ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 36ms
get tp. blocked users:
 1ms
others: 240ms
total:  351ms
созд. / загр.: 351ms
x
x
Закрыть


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