Алгоритм Дейкстры

@Leonsmoke · Регистрация: 26.02.2018

Студворк — интернет-сервис помощи студентам

Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше реализовать алгоритм Дейкстры на с++.
У меня есть двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа. Можете подсказать, как мне действовать и от чего плясать? Заранее спасибо

@LegionK · 27.05.2018, 11:34

Сообщение от Leonsmoke

двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа

Это же матрица смежности твоего графа?
Сначала можно посмотреть темы снизу или просто загуглить, все это давно есть

@LegionK · 27.05.2018, 11:49

C++

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    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";
    }
    pos[2] = 0;                // назначаем какую-то вершину началом алгоритма, узлом ( или так не говорят, хз)
    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];
            } // условие такое, если эта вершина не пройденная и она смежна с выбранной и если сумма веса выбранной вершины и ребра к текущей будет меньше, чем
        }     // вес текущей на данный момент, то  - меняем значение веса текущей вершины.
    }
    cout << pos[0] << "\n"; // теперь у нас в pos минимальные расстояния от выбранного узла к любой другой вершине
 
    cout << endl;
    return 0;
}

Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень

@Leonsmoke · 27.05.2018, 13:17 **[ТС]**

Спасибо огромное! Вы мне очень помогли

Добавлено через 1 час 16 минут

Сообщение от LegionK

Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень

А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135

@Ромаха · 27.05.2018, 14:33

Сообщение от Leonsmoke

А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135

Либо хранить. Вверху есть строчку p[j] = p[j]+что-то там
Заводите еще один vector<int> parent(n, -1);
И после этой строки вставляете parent[j] = i;

Вывод тогда будет таким

Код

while(pos != -1) {
   cout << pos << " ";
   pos = parent[pos];
}

Либо искать. Давайте представим, что граф неориентированный. Тогда это будет примерно так

Код

cout << pos << " ";
while(pos != №вершины от которой ищем) {
    for(int i = 0; i < n; i++)
       if (p[pos]==p[i]+matrix[pos][i]) {
          cout << i << " ";
          pos = i;
          break;
       }
}

@Leonsmoke · 28.05.2018, 13:34 **[ТС]**

Сообщение от Ромаха

cout << pos << " ";
while(pos != №вершины от которой ищем) {
for(int i = 0; i < n; i++)
if (p[pos]==p[i]+matrix[pos][i]) {
cout << i << " ";
pos = i;
break;
}
}

а что здесь за массив p?

Добавлено через 22 часа 29 минут
Вот что у меня получилось... ищет короткие пути из любой вершины в любую, но вот как сам путь найти я, хоть убейте, не допру

C++

for (i = 0; i<kolvo; i++)
    {
        distance[i] = INT_MAX; visited[i] = false;
    }
    distance[otkuda] = 0;
    for (count = 0; count<kolvo; count++)
    {
        int min = INT_MAX;
        for (i = 0; i<kolvo; i++)
            if (!visited[i] && distance[i] <= min)
            {
                min = distance[i]; index = i;
            }
        u = index;
        visited[u] = true;
        for (i = 0; i < kolvo; i++)
        {
            if (!visited[i] && dlins[u, i] && distance[u] != INT_MAX &&
                (distance[u] + dlins[u, i]) < distance[i])
            {
                distance[i] = distance[u] + dlins[u, i];
            }
            
        }
        
    }

@LegionK · 28.05.2018, 15:32

Leonsmoke, цитата с интернета : разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из s до любой вершины. Для этого достаточно так называемого массива предков: массива p[], в котором для каждой вершины v != s хранится номер вершины p[v], являющейся предпоследней в кратчайшем пути до вершины v. Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины v, а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной p[v], и этот путь будет кратчайшим для вершины p[v]. Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину s — так мы получим искомый кратчайший путь, но записанный в обратном порядке.

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины v происходит улучшение расстояния до некоторой вершины to, мы записываем, что предком вершины to является вершина v:

p[to] = v

Добавлено через 1 час 33 минуты
Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так :

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";
    }
    pos[0] = 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;
}

P.s Граф с той же фотографии

@Leonsmoke · 28.05.2018, 18:00 **[ТС]**

Сообщение от LegionK

Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так :

Разобрался! Наконец-то до меня дошло)) Спасибо Вам огромное

@Toshikshik · 09.12.2019, 18:54

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

C++

#include <iostream>
#include <vector>// для вектора
#include <algorithm>// для работы с алгоритмами (для reserve)
#include <fstream> //для вывода из файла
 
using namespace std;
 
int main()
{
system ("chcp 1251 ");
cout<<"Программа, выполняющая алгоритм Дейкстры"<<endl;
int a=1;
int menu;
int row;//кол-во вершин
int column;//кол-во вершин
int **matrix;
matrix= new int*[column];
 
int i,j;
 
while(a==1){
    cout<<"Выберите действие:"<<endl;
    cout<<"1.Ввести граф с клавиатуры"<<endl;
    cout<<"2.Ввести граф из файла  "<<endl;
    cout<<"3.Результат действия алгоритма до конкретной вершины"<<endl;
    cout<<"0.Завершить программу "<<endl;
    cout<<"Действие номер: ";
    cin>>menu;  
    
    
switch(menu){
    case 0:{
        a==0;
        delete[]matrix;
        break;
    }
    case 1:{
        cout<<"Введите количество вершин:"<<endl;
            cin>>column;
            row=column;
            matrix= new int*[row];
            for(int i=0; i<row; i++){
                matrix[i]= new int[column];
                matrix[row][column];
            }
            cout<<" "<<endl;
            cout<<"Сейчас вы заполняете матрицу с длинами ребер \n";
            for(int i = 0; i < column ; i++) { //заполнение
                for(int j = 0; j < row; j++){
                    cout <<"Введите элемент матрицы" << "[" << i << "][" << j << "]: ";
                    cin >> matrix[i][j];        
                }
            }
    cout << endl;
    cout<<"Введенная матрица:"<<endl;
        for(int i = 0; i < column ; i++) { //вывод
                for(int j = 0; j < row; j++){
                    cout << matrix[i][j]<<" ";     
                }
                cout<<endl;
            }
 
        
        break;
    }
    case 2:{
        cout << "Введенная матрица: "<<endl;
 
    ifstream in("matrix.txt");
    if (in.is_open()){
        int count = 0;//cчетчик
        int temp;
 
    while (!in.eof()){
        in >> temp;
        count++;
        }
 
    in.seekg(0, ios::beg);
    in.clear();
 
    int count_space = 0;
    char symbol;
    while (!in.eof()){
            
        in.get(symbol);
        if (symbol == ' ') count_space++;
        if (symbol == '\n') break;
    }
    
    in.seekg(0, ios::beg);
    in.clear();
 
     row = count / (count_space + 1);
     column = count_space + 1;
        
    for ( i = 0; i<row; i++) matrix[i] = new int[column];
 
    for ( i = 0; i < column; i++)
    for ( j = 0; j < column; j++)
    in >> matrix[i][j];
 
    for ( i = 0; i < column; i++){
        for ( j = 0; j < column; j++)
            cout << matrix[i][j]<<" ";
            cout << "\n";
    }
 
    in.close();
        
    }
    cout<<endl;
        break;
    }
    case 3:{
    int big_num=INT_MAX;//бесконечно большое число 
 
    int pose[row];//посещенные
    bool nepose[row];//непосещенные
    int min=0;
    int index_min=0;
    
            
        for(int i = 0;i<row;++i){ //заполняем массив посещенных бесконечно большими числами, непосещенные(временно присоед.) заполняются 0
 
            pose[i] = big_num;
            nepose[i] = false;
            parent[i] = -1;
        }
        cout << "Введенная матрица: "<<endl;
         for(int i = 0; i<row;++i){//вывод матрицы
            for(int j = 0;j<row;++j){
                cout << matrix[i][j]<<" ";
        }
        cout << "\n";
     }
    cout<<"Какую вершину считать узлом(корнем)?";
    cin>>pose[0];
    nepose[0]=true;
    
    
    cout << "\n";
    for(int i = 0; i<row-1;++i){
        min = big_num;
        
        for(int j = 0;  j<row-1;  ++j){
            if(!nepose[j] && pose[j] < min){// 
                min = pose[j];//минимальное значение вершины
                index_min = j;//индекс "минимальной" вершины
            }
        }
      
        nepose[j] = true;
        
        for(int j = 0;j<row;++j){
            if(!nepose[j] && matrix [index_min][j] > 0 && pose [index_min] != big_num && pose [index_min] + matrix [index_min][j] < pose[j]){
                pose [j] = pose [index_min] + matrix [index_min][j];
            }
        }
        
    }
    
  for(int i =0; i< row-1;i++ ){
 
    cout<<"Для вершины "<<i+1<<":"<<endl; 
    cout<<"Номера вершин пути:"<<endl;
    //ТУТ ДОЛЖЕН БЫТЬ ВЫВОД ПУТИ              
                            
                            
                            
                            
                            
                                
 cout << "\nКратчайший путь равен: " << pose[i+1] << "\n";
    cout << endl;
    }
  
    break;
    }
}   
}
    return 0;
}

@Leonsmoke 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 17
		1
	Алгоритм Дейкстры 27.05.2018, 11:12. Показов 68703. Ответов 8 Метки нет (Все метки) Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше реализовать алгоритм Дейкстры на с++. У меня есть двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа. Можете подсказать, как мне действовать и от чего плясать? Заранее спасибо 0

@LegionK 389 / 259 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	27.05.2018, 11:34	2
	Сообщение от Leonsmoke двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа Это же матрица смежности твоего графа? Сначала можно посмотреть темы снизу или просто загуглить, все это давно есть 0

@Leonsmoke 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 17
	27.05.2018, 13:17 [ТС]	4
	Спасибо огромное! Вы мне очень помогли Добавлено через 1 час 16 минут Сообщение от LegionK Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135 0

@Ромаха 353 / 134 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	27.05.2018, 14:33	5
	Сообщение от Leonsmoke А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135 Либо хранить. Вверху есть строчку p[j] = p[j]+что-то там Заводите еще один vector<int> parent(n, -1); И после этой строки вставляете parent[j] = i; Вывод тогда будет таким Код while(pos != -1) { cout << pos << " "; pos = parent[pos]; } Либо искать. Давайте представим, что граф неориентированный. Тогда это будет примерно так Код cout << pos << " "; while(pos != №вершины от которой ищем) { for(int i = 0; i < n; i++) if (p[pos]==p[i]+matrix[pos][i]) { cout << i << " "; pos = i; break; } } 1

@Leonsmoke 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 17
	28.05.2018, 18:00 [ТС]	8
	Сообщение от LegionK Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так : Разобрался! Наконец-то до меня дошло)) Спасибо Вам огромное 0

Опции темы

Алгоритм Дейкстры

Решение