Алгоритм Дейкстры нахождения кратчайшего пути

C, C++
#1

  1. как сделать так, чтобы программа могла считать и числа с плавающей запятой (double) ну то есть вычисление кратчайшего расстояния по алгоритму Дейкстры.

  2. Как выключить некоторые рёбра, пользователь сам выбирает какие ему рёбра не нужны в данный момент (граф неориентированный), то есть имеет рёбра без направлений.

Под числом с плавающей запятой подразумевается сумма чисел полученное по итогу выполнения алгоритма .

В программирование на c++ плохо разбираюсь.

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> parent(5, -1); // объявили и сразу заполнили -1-цами в кол-ве 5 штук
	int big_num(10000);
	int matrix[5][5] = { {0,5,12,0,0},
	{5,0,4,0,1},
	{12,4,0,2,0},
	{0,0,2,0,5},
	{0,1,0,5,0} };

	int pos[5], node[5], min(0), index_min(0);
	for (int i = 0; i < 5; ++i) {
		pos[i] = big_num;
		node[i] = 0;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) {
			cout << setw(4) << matrix[i][j];
		}
		cout << "\n";
	}
	int x;

	cout << "vvedite x1";

		cin >> x;
	pos[x - 1] = 0; // начальная точка 
	cout << "\n";
	for (int i = 0; i < 4; ++i) {
		min = big_num;
		for (int j = 0; j < 5; ++j) {
			if (!node[j] && pos[j] < min) {
				min = pos[j];
				index_min = j;
			}
		}
		node[index_min] = true;
		for (int j = 0; j < 5; ++j) {
			if (!node[j] && matrix[index_min][j] > 0 && pos[index_min] != big_num && pos[index_min] + matrix[index_min][j] < pos[j]) {
				pos[j] = pos[index_min] + matrix[index_min][j];
				parent.at(j) = index_min; // запоминаем предка вершины j
			}
		}
	}
	int n(0);
	cout << "\nnumber of top? : ";
	cin >> n;

	vector<int>temp; // n - 1, так как не забываем про индексацию
	for (int i = n - 1; i != -1; i = parent.at(i))temp.push_back(i + 1); // а все что здесь делается описано в справке,которую я те кинул
	reverse(temp.begin(), temp.end());
	for (int i = 0; i < temp.size(); ++i)cout << temp.at(i) << " ";

	cout << "\nWeight : " << pos[n - 1] << "\n";

	cout << endl;
	return 0;
}
#2

Это дискретная математика. Для старта кажется полной жопой, но не все так плохо как кажется на первый взгляд.
Составляйте алгоритм выполнения поставленной задачи, и если после составления алгоритма возникнут вопросы, обращайтесь, обязательно помогут…

#3

Здравствуйте, я с ней уже месяц пытаюсь разобраться, помогите пожалуйста, мне очень срочно ее надо, уже все сроки вышли

#4

А в чем проблема с ними? Так же как и int.

#5

Я не шарю, не понимаю как это сделать, выдает странные значения

#6

Так а что здесь шарить, шарить то по сути и не нужно.
Инты - целые численные значения (надеюсь это понятно, целые числа. 5 дллларов и 7 долларов это целые числа). С этим разобрались…
5 долляров и 5 центов это уже пошли флоаты…
А если считаем прибыль от наживы на медицине под игидой коронавируса, тогда подключаем “даблы” - там крайних не найдешь :slight_smile:

#7

Это-то понятно, просто когда меняю на доблы выдает кучу ошибок

#8

Копипаст ошибки в тему разговора…

#9

КОД

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	system("chcp 1251 > nul");

	vector<int> parent(5, -1); // объявили и сразу заполнили -1-цами в кол-ве 5 штук
	int big_num(10000);
	int matrix[5][5] = { {0,5,12,0,0},
	{5,0,4,0,1},
	{12,4,0,2,0},
	{0,0,2,0,5},
	{0,1,0,5,0} };

	double pos[5], node[5], min(0), index_min(0);
	for (int i = 0; i < 5; ++i) {
		pos[i] = big_num;
		node[i] = 0;
	}
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 5; ++j) {
			cout << setw(4) << matrix[i][j];
		}
		cout << "\n";
	}
	double x;

	cout << "Введите x1";

		cin >> x;
	pos[x - 1] = 0; // начальная точка 
	cout << "\n";
	for (int i = 0; i < 4; ++i) {
		min = big_num;
		for (int j = 0; j < 5; ++j) {
			if (!node[j] && pos[j] < min) {
				min = pos[j];
				index_min = j;
			}
		}
		node[index_min] = true;
		for (int j = 0; j < 5; ++j) {
			if (!node[j] && matrix[index_min][j] > 0 && pos[index_min] != big_num && pos[index_min] + matrix[index_min][j] < pos[j]) {
				pos[j] = pos[index_min] + matrix[index_min][j];
				parent.at(j) = index_min; // запоминаем предка вершины j
			}
		}
	}
	int n(0);
	cout << "\nКоличество вершин? : ";
	cin >> n;

	vector<int>temp; // n - 1, так как не забываем про индексацию
	for (int i = n - 1; i != -1; i = parent.at(i))temp.push_back(i + 1); // а все что здесь делается описано в справке,которую я те кинул
	reverse(temp.begin(), temp.end());
	for (int i = 0; i < temp.size(); ++i)cout << temp.at(i) << " ";

	cout << "\nWeight : " << pos[n - 1] << "\n";

	cout << endl;
	return 0;
}

ОШИБКИ

Серьезность Код Описание Проект Файл Строка Состояние подавления
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 46
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 36
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 48
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 48
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 48
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 48
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 49
Ошибка (активно) E2140 выражение должно относиться к целочисленному типу или типу перечисления без области видимости ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 49
Ошибка C2108 индекс имеет нецелый тип ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 37
Предупреждение C4244 =: преобразование “double” в “int”, возможна потеря данных ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 43
Предупреждение C4018 <: несоответствие типов со знаком и без знака ConsoleApplication1 C:\Users\79533\Desktop\Новая папка\ConsoleApplication1\ConsoleApplication1\ConsoleApplication1.cpp 62

#10

Зашибись…
На англецком можна, на языке (IDE)?

#11

Давайте

#12

Не дам.
Спросил…

#13

ахах, не допоняла
можете подсказать как?

#14

Для ночало:
поступить в ВУЗ…

#15

так, дальше

#16

Поступили?

#17

Приняли по проходному балу?

#18

поступили

#19

Приняли

#20

Что слушаем, лекции на какую тему?