Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вывести слова и длину каждого из этих слов http://www.cyberforum.ru/cpp-beginners/thread537181.html
Здравствуйте нужна помощь в корректировке кода, задача ниже, я сам понял как найти ВА и вывести сообщение , что ВА есть или нет!!! помогите пожалуйста, чтобы выполнялось требование задачи!! никак не...
C++ Задача на циклы. Начав тренировки, спортсмен в первый день пробежал 10 км. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый день он увеличивал дневную норму на 10% нормы предыдущего дня. Какой суммарный путь пробежит спортсмен за 7 дней? Помогите решить... http://www.cyberforum.ru/cpp-beginners/thread537180.html
Протабулировать функцию двух переменных C++
Протабулировать функцию y=f(u, v) на интервалах u есть и v является с шагами hu, hv. Результаты вывести в виде таблицы. y=cos(u*v)+sin(u*v), u является , v является , hu=1.5, hv=0.75 Найти сумму...
Проверить то, что все фразы в тексте начинаются с прописной буквы; при необходимости откорректировать текст. C++
Задача на Си. Текст не содержит собственных имен и сокращений, набран с использованием прописных и строчных русских букв. Проверить то, что все фразы (и только они) начинаются с прописной буквы; при...
C++ Заполнять массив особым образом (для МНК) http://www.cyberforum.ru/cpp-beginners/thread537166.html
Вот такая вот прога. ПРизвана заполнять массив особым образом(для МНК), но часть массива заполняется белибердой. ЧТо с этим делать? У ма не приложу, в чём проблема. Помогите, пожалуйста. int main()...
C++ Начал изучать С по книге, вроде обещали С++, но... В общем начал изучать С по книге, вроде обещали С++, но, помоему, он маленько по другому выглядет. Пример: printf("AaaAaAA") ; Или: scanf("%d", Num) ; Так же тута есть Постинкременты и... подробнее

Показать сообщение отдельно
Allegas
0 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 8

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

02.04.2012, 21:56. Просмотров 1010. Ответов 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; 
}
Буду благодарен за помощь в прикручивании связного списка и файла со списком смежности к этой проге.
Если существует другой алгоритм так же буду благодарен
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru