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

Порядок вершин при поиске кратчайшего пути - C++

Восстановить пароль Регистрация
 
Nazgul94
1 / 1 / 0
Регистрация: 22.11.2012
Сообщений: 24
05.10.2013, 15:13     Порядок вершин при поиске кратчайшего пути #1
Есть алгоритм Дейкстры для поиска кратчайшего пути между вершинами. Прога ищет путь правильно и выдает число равное длине минимального пути, но никак не могу правильно сохранить сами номера вершин для их вывода(т.е. порядок вершин в кратчайшем пути). Не знаю в чем дело какие только условия отбора вершин не ставил, не могу придумать, не хватает опыта в программировании.

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
#include <iostream>
#include <sstream>
 
using namespace std;
 
///////////////////////////////
 
int arr[100][100];   //массив весов ребер
bool USED[100];  //логический массив расмотренных вершин
int DIST[100];  //массив длин пути
int MAX = 999999999; //метка бесконечности
char b; //вспомогательная переменная
int mass[100];
string str;
int m[100];
bool chang = false;
int k;
 
void ShowWay(int* m) //функция вывода пути
{   
    /*for(int i=0; i < s.length(); i++)
        cout << "--> " << s[i];*/
    for(int i=1; i < 100; i++)
    { 
      cout << m[i];
      if(m[i] != 0)
        cout << " --> " << m[i]; 
      else break;
    }
 
}
int main()
{setlocale(LC_ALL,"RUS");
    int x=0, y=0, E=0; 
    //x-из какой вершины, y-в какую вершину, E-вес ребра соединяющего вершины x и y 
    int n,r,S,T; 
    //n-количество вершин в графе, r-количество ребер, S-вершина из которой ищем кратчайший путь, T-вершина куда мы ищем этот самый путь
    cout << "Введите количество вершин: "; cin >> n; //вводим данные
    cout << "Введите количество ребер: "; cin >> r;
    cout << "Введите номер вершины S: "; cin >> S; S--; //начальная вершина будет меньше на 1 т.к. нумерация в массиве идет с 0 
    cout << "Введите номер вершины T: "; cin >> T; T--;      //тоже самое
    int V = S, K = S;
    for (int i=0; i < n; i++) 
       { DIST[i] = MAX; } //инициализируем метку кратчайшего пути "бесконечностью"
    for (int i=0; i < n; i++) 
    { mass[i] = 0; }
    for (int i=0; i < r; i++)
       { 
         cout << "Введите иходную вершину, конечную и растояние между ними( x - y - E )";
         cin >> x >> b >> y >> b >> E; 
         arr[x-1][y-1] = E; //arr[y-1][x-1] = E;
       }
    DIST[S] = 0; //крат-й путь начальной вершины
    while (true) // "бесконечный цикл"
    {
      int from = 0, from_E = MAX;
        for (int i=0; i < n; i++)
            if ((from_E > DIST[i]) && !(USED[i])) //если вес крат-го пути i-й вершины меньше MAX и она не рассмотрена, то ...
               { from = i; from_E = DIST[i]; }  
            if (from_E >= MAX) break; //выход из цикла while 
            USED[from] = true;  //делаем вершину раасмотренной
            int min = 0; chang = false;
        for(int to=0; to < n; to++)
          {
              if (arr[from][to] != 0) 
                if ((!USED[to]) && (DIST[to] > (DIST[from] + arr[from][to]))) 
                   {
                       DIST[to] = DIST[from] + arr[from][to];  //устанавливаем метку крат-го пути с учетом предыдущей вершины                                 
                   } 
                if((min < DIST[to]) & (from == V))   //если вершина из которой мы наблюдаем с постоянной меткой
                         { min = DIST[to]; V = to; chang = true; } 
          }
         if(chang == true) // если значение V поменялось записываем в массив
          {
             m[k] = V + 1;
             k++;
          }
    }
    if (DIST[T] < MAX) //вывод ответа
    { cout << "Кратчйший путь: "; ShowWay(m); cout << "\nДлина пути: " << DIST[T] << endl; } 
     else cout << "Нет пути!!!"; 
 
system("pause");
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 15:13     Порядок вершин при поиске кратчайшего пути
Посмотрите здесь:

C++ Поиск кратчайшего пути на клетчатом поле.
Поиск кратчайшего пути в графе C++
Восстановление кратчайшего пути в графе C++
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
C++ Нахождение кратчайшего пути, поиск с возвратом
Поиск кратчайшего пути (рекурсия) C++
C++ Нахождение кратчайшего пути
Поиск кратчайшего пути на графе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2769 / 1582 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
05.10.2013, 15:44     Порядок вершин при поиске кратчайшего пути #2
Где обновляешь расстояние в DIST, там ещё надо сохранять предыдущую вершину в другом массиве. Потом по цепочке предыдущих вершин можно найти путь, начиная с конца.
Yandex
Объявления
05.10.2013, 15:44     Порядок вершин при поиске кратчайшего пути
Ответ Создать тему
Опции темы

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