Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 04.09.2019
Сообщений: 3
1

Как можно модифицировать алгоритм Дейкстры под поиск самого длинного пути?

14.09.2019, 19:55. Показов 1182. Ответов 8
Метки нет (Все метки)

C++ (Qt)
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
#include <iostream>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
int N;
 
int main() {
  setlocale(LC_ALL, "Rus");
  cout << "Введите количество вершин\n";
  cin >> N;
  int linksMatrix[N][N]; // Матрица связей
  int minMas[N];         // Минимальное расстояние
  int verMas[N];         // Посещенные вершины
  int tmp;
  int minindex, min;
 
  for (int i = 0; i < N; i++) {
    linksMatrix[i][i] = 0; // Инициализация матрицы связей
    for (int j = i + 1; j < N; j++) {
      printf("Введите расстояние %d - %d: ", i + 1, j + 1);
      scanf("%d", &tmp);
      linksMatrix[i][j] = tmp;
      linksMatrix[j][i] = tmp;
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) // Вывод матрицы связей
      printf("%5d", linksMatrix[i][j]);
    printf("\n");
  }
  for (int i = 0; i < N; i++) {
    minMas[i] = 10000; //Инициализация вершин и расстояний
    verMas[i] = 1;
  }
  minMas[0] = 0;
  do {
    minindex = 10000;
    min = 10000;
    for (int i = 0; i < N; i++) {
      if ((verMas[i] == 1) && (minMas[i] < min)) {
        min = minMas[i];
        minindex = i;
      }
    }
    if (minindex != 10000) {
      for (int i = 0; i < N; i++) {
        if (linksMatrix[minindex][i] > 0) {
          tmp = min + linksMatrix[minindex][i]; //Минимальный найденные вес
          if (tmp < minMas[i]) { //
            minMas[i] = tmp; // Сравниваем с минимальным весом вершины
          }
        }
      }
      verMas[minindex] = 0;
    }
  } while (minindex < 10000);
 
int con = 10;
while (con != 0) { // Восстановление пути
  int vertex[N];   // Массив посещенных вершин
  int endPoint;    // Индекс конечной вершины
  cout << "\nИндекс конечной вершины = ";
  cin >> endPoint;
  con = endPoint;
  endPoint -= 1;
  int vend =
      minMas[endPoint + 1]; // vend-Для проверки на не превышение значения 10000
  vertex[0] = endPoint + 1; // Начальный элемент - конечная вершина
  int k = 1; // Индекс предыдущей вершины
  int weight = minMas[endPoint]; // Вес конечной вершины
 
  while (endPoint > 0) // Пока не дошли до начальной вершины
  {
    if (vend == 10000)
      break;
    for (int i = 0; i < N; i++) // Просматриваем все вершины
      if (linksMatrix[endPoint][i] != 0) // Если есть связь
      {
        int tmp =
            weight -
            linksMatrix[endPoint][i]; // Определяем вес вершины из предыдущей
        if (tmp == minMas[i]) // Если вес совпал с рассчитанным
        { // Значит из этой вершины был переход
          weight = tmp; // Сохраняем новый вес
          endPoint = i; // Сохраняем предыдущую вершину
          vertex[k] = i + 1; // И записываем её в массив
          k++;
        }
      }
  }
 
  if (vend < 10000) { // Вывод пути (начальная вершина оказалась в конце
                      // массива из k - элементов)
    printf("\nВывод кратчайшего пути\n");
    printf("%3d", vertex[k - 1]);
    for (int i = k - 2; i >= 0; i--)
      printf("-->%3d ", vertex[i]);
    printf("\nРасстояние равное = %3d", vend);
  } else
    printf("Пути к этой вершине не существует");
}
getchar();
return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.09.2019, 19:55
Ответы с готовыми решениями:

Поиск самого длинного пути
На вход подается двумерный числовой массив. Требуется написать программу (возможно, из нескольких...

Поиск самого длинного пути в графе
Есть граф заданный матрицей смежности размера n. В этом графе место стыка обозначается 1. Нужно...

Поиск самого длинного пути расположения файла
помогите с задачей по файлам задача такая Определить и вывести самый длинный путь (включая имя...

поиск пути. алгоритм Дейкстры
доброго времени суток) обработка графа реализована через 2 динамических массива и процедуру...

8
Эксперт C
25592 / 15962 / 3418
Регистрация: 24.12.2010
Сообщений: 34,913
14.09.2019, 20:19 2
Nero_Wulf, .один из способов. Найти максимальное расстояние M. И в матрице расстояний заменить расстояние на M - расстояние.
Наверное, можно ничего не заменять. Но в коде вместо расстояние использовать именно M - r.
PS. Кода не смотрел.
0
302 / 214 / 74
Регистрация: 23.05.2011
Сообщений: 970
14.09.2019, 20:41 3
Nero_Wulf, а как понять самый длинный путь?
В графе с циклами можно построить путь бесконечной длины.
0
0 / 0 / 0
Регистрация: 04.09.2019
Сообщений: 3
14.09.2019, 20:42  [ТС] 4
Путь, который проходит через вершину графа не более одного раза
0
670 / 286 / 99
Регистрация: 04.07.2014
Сообщений: 807
14.09.2019, 23:07 5
Цитата Сообщение от Nero_Wulf Посмотреть сообщение
Путь, который проходит через вершину графа не более одного раза
Задача коммивояжёра?
Но она NP-трудная. И если ты решишь её алгоритмом Дейкстры то докажешь P=NP!!!
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
15.09.2019, 00:36 6
Цитата Сообщение от Nero_Wulf Посмотреть сообщение
Как можно модифицировать алгоритм Дейкстры под поиск самого длинного пути?
Заменить на максимум. Вот и все.
0
670 / 286 / 99
Регистрация: 04.07.2014
Сообщений: 807
15.09.2019, 00:59 7
Цитата Сообщение от Ромаха Посмотреть сообщение
Заменить на максимум. Вот и все.
И что ты найдёшь? Максимальный из коротких, и то не всех?
0
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
18.09.2019, 01:16 8
Цитата Сообщение от AlexVRud Посмотреть сообщение
И что ты найдёшь? Максимальный из коротких, и то не всех?
Почему же?
Теперь каждый раз ин канвы будет выбирать оптимальное ребро. Путь до вершины будет лочиться. И за счет оптимального состояние на предыдущей итерации - это будет оставаться оптимальной.
Где я неправ?
0
670 / 286 / 99
Регистрация: 04.07.2014
Сообщений: 807
20.09.2019, 15:08 9
Цитата Сообщение от Ромаха Посмотреть сообщение
Где я неправ?
Хорошо, вот пару тестовых примеров (каждое ребро единичной длины в обе стороны), ждём код
Как можно модифицировать алгоритм Дейкстры под поиск самого длинного пути?
Как можно модифицировать алгоритм Дейкстры под поиск самого длинного пути?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.09.2019, 15:08

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Как модифицировать алгоритм Дейкстры
Здравствуйте! Как модифицировать алгоритм Дейкстры, чтобы искать кратчайшие пути среди тех, где не...

Поиск самого длинного пути от первой до последней вершины ацикличного ориентированного невзвешенного графа
Здравствуйте! Есть задача найти самый длинный путь от первой до последней вершины ацикличного...

Алгоритм Дейкстры (поиск кратчайшего пути в графе)
Доброго времени суток! Пытаюсь разобраться в алгоритме Дейкстры по книжке &quot;Грокаем алгоритмы&quot;,...

Не понимаю такой алгоритм (поиск самого длинного слова в файле)
f = &quot;sex rock dragndrop a get pock laaaaaaaaaaaa gas&quot; s = max(map(lambda x: (len(x), x), f.split(&quot;...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.