Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Дейкстры в связном списке + файлы. - C++

Восстановить пароль Регистрация
 
Allegas
0 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 8
02.04.2012, 21:56     Алгоритм Дейкстры в связном списке + файлы. #1
Задача такова :
Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайшие маршруты из заданного города в остальные. Граф задан списками смежности, хранящимися в текстовом файле

Тут уже нашел алгоритм Дейкстры для простого массива :

C++
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// Алгоритм Дейкстры
// нахождение наименьшего расстояяния от заданной точки 
// до всех остальных
#include<iostream.h> 
#include<conio.h> 
 
#define M ( sizeof(cities)/sizeof(cities[ 0 ]) )
#define N ( sizeof(inf)/sizeof(inf[ 0 ]) )
 
//якобы бесконечность, данное число должно быть больше
//максимального расстояния (по правилам алгоритма)
#define INFINITY 10000
//от какой точки пляшем :)
#define dance 2
 
//пункты
char cities[ ][ 50 ]={ "A", "B", "C", "D", "E", "F" };
struct
{
    char points[ 2 ][ 50 ]; //от пункта к пункту
    int distance;           //расстояние км
    }inf[ ]={
    {{ "A", "B" }, 65 },
    {{ "B", "C" }, 40 },
    {{ "C", "D" }, 60 },
    {{ "D", "E" }, 68 },
    {{ "E", "A" }, 32 },
    {{ "A", "F" }, 45 },
    {{ "B", "F" }, 25 },
    {{ "C", "F" }, 40 },
    {{ "D", "F" }, 60 },
    {{ "E", "F" }, 50 },
    };
 
struct range
{
    char *point;    //пункт
    int distance;   //расстояние от начальной точки
    };
  
int main() 
{
int i, j, c, current_distance, q, p, real_p;
char *current_city=NULL;
 
range *xr=new range[ M ];
//расстояние от стартовой точки до остальных изначально
//равно бесконечности
for( i=0; i<M; i++ )
{
    xr[ i ].point=NULL;
    xr[ i ].distance=INFINITY;
    }
//а начальная имеет значение ноль
xr[ 0 ].distance=0;
xr[ 0 ].point=cities[ dance ];
 
for( i=0, c=0, p=1; i<M; i++ )
{
    current_city=xr[ i ].point;
 
    for( j=0, real_p=1; j<N; j++ )
    {
        current_distance=xr[ i ].distance;
        if( strcmp(inf[ j ].points[ 0 ], current_city)==0
        ||  strcmp(inf[ j ].points[ 1 ], current_city)==0 )
        {
            //проверка не проверяли ли эту точку ранее
            for( q=0; q<i; q++ )
                if( strcmp(inf[ j ].points[ 0 ], xr[ q ].point)==0
                ||  strcmp(inf[ j ].points[ 1 ], xr[ q ].point)==0 )
                    break;
            if( q<i )
                continue;
 
           //-----------------------------
           //находим какая точка сейчас явл соседом с той которую
           //проверяем т.е до какой точки смотрим расстояние
           for( q=0; q<2; q++ )
              if( strcmp(inf[ j ].points[ q ], current_city)!=0 )
                  break;
 
           //i -- текущий пункт
           //p -- всего соседей(уже посещенных) 
           //real_p -- сосед текущего пункта который сейчас проверяется
           //j -- текущий отрезок
  
           for( c=0; c<p; c++ )
               if( strcmp(xr[ c ].point, inf[ j ].points[ q ])==0 )
                   break;
           if( c<p )
               real_p=c; //пункт посещался сверяться будем с ним  
           else
           {   //пункт не посещался
               xr[ p ].point=inf[ j ].points[ q ]; //запоминаем пункт
               real_p=p; //вносим свежие данные по нему
               ++p;
               }
  
           current_distance+=inf[ j ].distance;
           if( current_distance<xr[ real_p ].distance )
               //запоминаем расстояние
               xr[ real_p ].distance=current_distance;
              }
          }
      }
  
cout << endl << "---------------------" << endl
     << "Beeline from " << xr[ 0 ].point << endl;
for( q=1; q<p; q++ )
    cout << "to: " << xr[ q ].point << " = " << xr[ q ].distance << endl;
delete [] xr; 
getch();
return 0; 
}
Буду благодарен за помощь в прикручивании связного списка и файла со списком смежности к этой проге.
Если существует другой алгоритм так же буду благодарен
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2012, 21:56     Алгоритм Дейкстры в связном списке + файлы.
Посмотрите здесь:

C++ Пузырёк на связном списке
быстрая сортировка на связном списке в С++ C++
C++ Как в связном списке присвоить NULL полю next, если тип этого поля не указатель, а ссылка?
Copy-Constructor В Шаблонном Связном списке C++
Как в связном списке обратиться к элементу по адресу C++
C++ Исправить ошибки в связном списке
непонятка в связном списке C++
Передать значение из одной функции в другую функцию в связном списке C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Allegas
0 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 8
03.04.2012, 22:14  [ТС]     Алгоритм Дейкстры в связном списке + файлы. #2
Апчик
Yandex
Объявления
03.04.2012, 22:14     Алгоритм Дейкстры в связном списке + файлы.
Ответ Создать тему
Опции темы

Текущее время: 14:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru