Всем привет. Срочно нужна помощь. Уже через часов 8 сдавать лабу, помогите пожалуйста, готовым кодом.
Задача: Задан простой взвешенный граф (или орграф) с помощью весовой матрицы смежности вершин. Найти алгоритмом Дейкстры кратчайший путь между двумя заданными вершинами. Вывести сам путь и его вес. В случае отсутствия пути вывести соответствующее сообщение.
Я нашёл программу, которая считывает из консоли веса для рёбер(дуг) и из них формируют матрицу. Я передал, чтобы программа считывала матрицу из файла. (На всякий случай старый код просто закомментировал)
Моя программа ниже:
| 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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
| #define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std ;
int SIZE;
int main()
{
setlocale(LC_ALL, "RUSSIAN");
//Создаем файловый поток и связываем его с файлом
ifstream in("input.txt");
if (in.is_open()){
//Если открытие файла прошло успешно
//Вначале посчитаем сколько чисел в файле
int count = 0;// число чисел в файле
int temp1;//Временная переменная
while (!in.eof())// пробегаем пока не встретим конец файла eof
{
in >> temp1;//в пустоту считываем из файла числа
count++;// увеличиваем счетчик числа чисел
}
//Число чисел посчитано, теперь нам нужно понять сколько
//чисел в одной строке
//Для этого посчитаем число пробелов до знака перевода на новую строку
//Вначале переведем каретку в потоке в начало файла
in.seekg(0, ios::beg);
in.clear();
//Число пробелов в первой строчке вначале равно 0
int count_space = 0;
char symbol;
while (!in.eof())//на всякий случай цикл ограничиваем концом файла
{
//теперь нам нужно считывать не числа, а посимвольно считывать данные
in.get(symbol);//считали текущий символ
if (symbol == ' ') count_space++;//Если это пробел, то число пробелов увеличиваем
if (symbol == '\n') break;//Если дошли до конца строки, то выходим из цикла
}
//cout << count_space << endl;
//Опять переходим в потоке в начало файла
in.seekg(0, ios::beg);
in.clear();
//Теперь мы знаем сколько чисел в файле и сколько пробелов в первой строке.
//Теперь можем считать матрицу.
SIZE = count / (count_space + 1);//число строк
int a[SIZE][SIZE]; // матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
// // Инициализация матрицы связей
// for (int i = 0; i<SIZE; i++){
// a[i][i] = 0;
// for (int j = i + 1; j<SIZE; j++) {
// printf("Введите расстояние %d - %d: ", i + 1, j + 1);
// scanf("%d", &temp);
// a[i][j] = temp;
// a[j][i] = temp;
// }
// }
// // Вывод матрицы связей
// for (int i = 0; i<SIZE; i++){
// for (int j = 0; j<SIZE; j++)
// printf("%5d ", a[i][j]);
// printf("\n");
// }
for (int i=0; i < SIZE; i++){
for (int j=0; j<SIZE; j++){
in >> a[i][j];
};
};
for (int i=0; i < SIZE; i++){
for (int j=0; j<SIZE; j++){
cout << a[i][j] << '\t';
};
cout << endl;
};
//Инициализация вершин и расстояний
for (int i = 0; i<SIZE; i++){
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
// Шаг алгоритма
do {
minindex = 10000;
min = 10000;
for (int i = 0; i<SIZE; i++){ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]<min)){ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000){
for (int i = 0; i<SIZE; i++){
if (a[minindex][i] > 0){
temp = min + a[minindex][i];
if (temp < d[i]){
d[i] = temp;
}
}
}
v[minindex] = 0;
}
}
while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n");
for (int i = 0; i<SIZE; i++)
printf("%5d ", d[i]);
// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 - 1
ver[0] = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i<SIZE; i++) // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
{
int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод кратчайшего пути\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
}
else{
cout << "Error!";
}
return 0;
} |
|
(
