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

Выкладываю реализацию алгоритма Дейкстры на С++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 128, средняя оценка - 4.85
abd256
8 / 8 / 0
Регистрация: 08.01.2011
Сообщений: 9
09.01.2011, 11:12     Выкладываю реализацию алгоритма Дейкстры на С++ #1
Дпанная программа выполняет поиск по заданной матрице весов. Далее указываем начальную точку в графе и программа расчитывает все кратчайшие растояния от начальной точки до остальных следующим видом:путь от нач. точки до n-ой: - n-ая промежуточная промежуточная... начальная, вес пути - х. долго искал подобный алгоритм но так и не нашел. вот выкладываю что получилось.Прошу строго не судить(на основе алгоритма Флойда)
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
#include <iostream.h>
#include <conio.h>
#include <windows.h>
#include<iomanip.h>
    
char NEWT[256];
char*RUS(char*TEXT) {
CharToOem(TEXT,NEWT);
return NEWT;}
 
int v;
int main()
{   int i,j;
   int infinity=1000;                     // Бесконечность
                                          // Количество вершин в графе
   int VES[100][100];                         // Матрица весов графа
 
   int x[100];                            //Массив, содержащий единицы и нули для каждой вершины,
                                          // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                                          // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   
   int DlinaPuti[100];                    //t[i] - длина кратчайшего пути от вершины s в i
 
   int PredVertex[100];                   //h[i] - вершина, предшествующая i-й вершине
                                          //на кратчайшем пути
   int VERTEX;
   int p;                         
cout<<RUS("Ввести количество вершин в графе ")<<endl;
cin>>VERTEX;p= VERTEX;                    //Число вершин в графе
cout<<RUS("Заполните матрицу весов графа ")<<endl;      // Матрица весов графа
cout<<setw(4);
for (i=0;i<VERTEX;i++)
cout<<RUS("|x")<<i+1;
cout<<endl;
 
for(i=0;i<VERTEX;i++)
{cout<<RUS("X")<<i+1<<'|';
for(j=0;j<VERTEX;j++)
cin>>VES[i][j];}
 
                                        // Будем искать путь из вершины s в вершину g по циклу
   int start;                           // Номер исходной вершины
   int end;                             // Номер конечной вершины
N: cout<<RUS("Введите стартовую вершину: ");    // Номер может изменяться от 0 до p-1
   cin>>start;
   if (start>(p-1) && start<0) {cout<<RUS("Нет такой вершины повторите ввод...")<<endl; goto N; } // на случай неверных данных
   start=start-1;                       //так как массив начинается с 0 отнимаем от вводимой цифры 1
   for (int prosto=0;prosto<VERTEX;prosto++)
   {end=prosto;                         //цикл прогоняет алгоритм Флойда p-ое количество раз преврашая его в алгоритм Дейкстры  
   if (end==start) continue;            //исключаем просчет растояния между одной и той же точкой
   else
   {
 
                                         // Инициализируем начальные значения массивов
   int u;                                // Счетчик вершин
   for (u=0;u<p;u++)
   {
       DlinaPuti[u]=infinity;                    //Сначала все кратчайшие пути из s в i 
                                         //равны бесконечности
      x[u]=0;                            // и нет кратчайшего пути ни для одной вершины
   }
   PredVertex[start]=0;                     // s - начало пути, поэтому этой вершине ничего не предшествует
   DlinaPuti[start]=0;                      // Кратчайший путь из s в s равен 0
   x[start]=1;                              // Для вершины s найден кратчайший путь
   v=start;                                 // Делаем s текущей вершиной
   
   while(1)
   {
                                        // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(VES[v][u]==0)continue;      // Вершины u и v несмежные
         if(x[u]==0 && DlinaPuti[u]>DlinaPuti[v]+VES[v][u]) //Если для вершины 'u' еще не 
                                        //найден кратчайший путь
                                        // и новый путь в 'u' короче чем 
                                        //старый, то
         {
            DlinaPuti[u]=DlinaPuti[v]+VES[v][u];            //запоминаем более короткую длину пути в
                                        //массив t[и]
           PredVertex[u]=v;                     //запоминаем, что v->u часть кратчайшего 
                                        //пути из s->u
         }
      }
 
                                         // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;                   // Для поиска самого короткого пути
      v=-1;                             // В конце поиска v - вершина, в которую будет 
                                        // найден новый кратчайший путь. Она станет 
                                        // текущей вершиной
      for(u=0;u<p;u++)                  // Перебираем все вершины.
      {
         if(x[u]==0 && DlinaPuti[u]<w)           // Если для вершины не найден кратчайший 
                                         // путь и если длина пути в вершину 'u' меньше
                                         // уже найденной, то
         {
            v=u;                         // текущей вершиной становится 'u'-я вершина
            w= DlinaPuti[u];
         }
      }
      if(v==-1)
      {
         cout<<RUS("Нет пути из вершины ")<<start+1;cout<<RUS(" в вершину ")<<end+1<<"."<<endl;
         break;
      }
      if(v==end)                            // Найден кратчайший путь,
      {                                 // выводим его
         cout<<RUS("Кратчайший путь из вершины ")<<start+1;cout<<RUS(" в вершину ")<<end+1<<":";
       u=end;
       while(u!=start)
         {
            cout<<" "<<u+1;
            u=PredVertex[u];
         }
         cout<<" "<<start+1<<RUS(". Длина пути - ")<< DlinaPuti[end];cout<<endl;
       break;
      }
      x[v]=1;
   }}}
   
return 0;}
Добавлено через 1 минуту
Надеюсь людям понравится
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2011, 11:12     Выкладываю реализацию алгоритма Дейкстры на С++
Посмотрите здесь:

Алгоритм Дейкстры C++
C++ пытаюсь сделать реализацию через считывание из файла кол-ва чисел, i,но незнаю как сделать реализацию из файла в массив и сортировки.
Задача с использованием алгоритма Дейкстры C++
C++ Подскажите пожалуйста как написать реализацию алгоритма
C++ Параллельная реализация алгоритма Дейкстры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
genrich
Сообщений: n/a
02.05.2011, 14:22     Выкладываю реализацию алгоритма Дейкстры на С++ #2
спасибо-все отлично работает, а как сделать так что бы матрица вводилась не с клавиатуры, а из файла ?
abd256
8 / 8 / 0
Регистрация: 08.01.2011
Сообщений: 9
03.05.2011, 13:44  [ТС]     Выкладываю реализацию алгоритма Дейкстры на С++ #3
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
// прототипы
void infile (int **VES,int num); //вводим из файла
int size();                            //вводим размер матрицы
 
//в main
 
n=size();
VES=new int *[n];
for (i=0;i<n;i++)                                    
VES[i]=new int[n];
infile(VES,n);
 
// main кончается
int size()
{   int n;
    ifstream in;//открываем поток in для ввода данных из файла
    in.open("n.txt",ios::nocreate);//связываем поток ввода in с файлом input.txt, если этот файл существует
    if(in.fail()) {
        cout<<RUS("Файла не существует...\n");
        exit(1);}//если файл не существует, на экран выводится сообщение об ошибке и программа закрываетс
    in>>n;  //вводим из файла n.txt данные в переменную 
    in.close();//закрываем поток ввода из файла in
    return n;//возвращаем полученное значение n в главную функцию
}
 
//////////////////////////////////////////////////////////////////////////////////
 
void infile (int **VES, int n){
    ifstream in;                        //открываем поток in для ввода данных из файла}
    in.open("input.txt",ios::nocreate);//связываем поток ввода in с файлом input.txt, если этот файл существует
    
    if(in.fail()) {
        cout<<RUS("Файла не существует...\n");      
        exit(1);}//если файл не существует, на экран выводится сообщение об ошибке и программа закрывается
    for (int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        in>>VES[i][j];//вводим из файла "input.txt" массив VES
    in.close();//закрываем поток ввода из файла in
}

как то так
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
19.12.2011, 03:46     Выкладываю реализацию алгоритма Дейкстры на С++ #4
Ошибка (Function 'CharToOem' should have a prototype) в 8 строке вашей программы, не подскажите как исправить?
Defaillance
 Аватар для Defaillance
0 / 0 / 0
Регистрация: 23.09.2012
Сообщений: 16
20.04.2013, 22:33     Выкладываю реализацию алгоритма Дейкстры на С++ #5
У меня тоже ошибка в 8-й строке
error C2664: CharToOemW: невозможно преобразовать параметр 1 из "char *" в "LPCWSTR"
Типы, на которые указывают указатели, не связаны; для преобразования требуется reinterpret_cast, приведение в стиле С или приведение в стиле функции
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11832 / 6811 / 769
Регистрация: 27.09.2012
Сообщений: 16,887
Записей в блоге: 2
Завершенные тесты: 1
21.04.2013, 02:50     Выкладываю реализацию алгоритма Дейкстры на С++ #6
Цитата Сообщение от Defaillance Посмотреть сообщение
error C2664: CharToOemW: невозможно преобразовать параметр 1 из "char *" в "LPCWSTR"
Отключите Юникод в настройках проекта.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.04.2013, 07:39     Выкладываю реализацию алгоритма Дейкстры на С++ #7
как-то у вас все запутанно.
посмотрите на этот вариант.
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
п»їп»ї#include <vector>
#include <iostream>
using namespace std;
 
#define im 2000000000
 
int main()
{
    int f, n, s;
    cin >> n;
    cin >> s;
    cin >> f;
    vector <bool> used;
    vector <int> distance;
    vector <int> parents(n);
    vector <vector <int>> g(n);
    
    used.assign(n, 0);
    distance.assign(n, im);
    distance[s-1] = 0;
    for(int i=0; i < n; i++)
        g[i].assign(n, 0);
    
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
            cin >> g[i][j];
    
    for(int i=0; i < n; i++)
    {
        int v = -1;
        for(int j=0; j < n; j++)
            if(used[j] == false && (v == -1 || distance[j] < distance[v]))
                v = j;
        used[v] = true;
        for(int j=0; j < n; j++)
            if(g[v][j] != -1 && distance[v]+g[v][j] < distance[j])
            {
                parents[j] = v;
                distance[j] = distance[v]+g[v][j];
            }
    }
    if(distance[f-1] != im)
        cout << distance[f-1] << endl;
    else
        cout << -1 << endl;
    //system("pause");
    return 0;
}
Добавлено через 3 минуты
не обращайте внимания на ерунду в первой строке... какая-то фигня при вставке случилась.
0x10
21.04.2013, 08:03
  #8

Не по теме:

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

Krock21rus
73 / 73 / 19
Регистрация: 18.11.2013
Сообщений: 369
Завершенные тесты: 2
30.01.2014, 13:45     Выкладываю реализацию алгоритма Дейкстры на С++ #9
Цитата Сообщение от 0x10 Посмотреть сообщение

Не по теме:

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

согласен, алгоритм вроде рабочий, но кажется лучше сделать цикл while чем использовать goto, и измение x я нашёл только в конце, что-то тут не так

Добавлено через 3 минуты
а вот сам алгоритм дейкстры, который находит расстояние от начальной точки до всех остальных. Нашёл в интернете на kvodo.ru, необходимо передать матрицу расстояний и начальную точку, компактный:

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
void Dijkstra(int GR[V][V], int st)
{
int distance[V], count, index, i, u, m=st+1;
bool visited[V];
for (i=0; i<V; i++)
{
distance[i]=INT_MAX; visited[i]=false;
}
distance[st]=0;
for (count=0; count<V-1; count++)
{
int min=INT_MAX;
for (i=0; i<V; i++)
if (!visited[i] && distance[i]<=min)
{
min=distance[i]; index=i;
}
u=index;
visited[u]=true;
for (i=0; i<V; i++)
if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&
distance[u]+GR[u][i]<distance[i])
distance[i]=distance[u]+GR[u][i];
}
cout<<"Стоимость пути из начальной вершины до остальных:\t\n";
for (i=0; i<V; i++) if (distance[i]!=INT_MAX)
cout<<m<<" > "<<i+1<<" = "<<distance[i]<<endl;
else cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl;
}
mastercook2
0 / 0 / 0
Регистрация: 27.10.2015
Сообщений: 13
28.11.2016, 14:53     Выкладываю реализацию алгоритма Дейкстры на С++ #10
Ребят, можете переделать код, чтобы задавать две вершины и программа выводила кратчайший путь до них, на с++ новичок, пытался сам переделать ничего не получается, а скоро сдавать курсовую по дейкстре, очень нужно, может найдется добрый человек, который поможет, спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2016, 17:52     Выкладываю реализацию алгоритма Дейкстры на С++
Еще ссылки по теме:

C++ Реализация алгоритма Дейкстры
C++ Алгоритм Дейкстры
Определение радиуса и соответствующего радиусу пути взвешенного орграфа на основе алгоритма Дейкстры C++

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

Или воспользуйтесь поиском по форуму:
mastercook2
0 / 0 / 0
Регистрация: 27.10.2015
Сообщений: 13
30.11.2016, 17:52     Выкладываю реализацию алгоритма Дейкстры на С++ #11
Привет, мне понравился твой алгоритм, ты не мог бы помочь мне, переделав немного этот алгоритм в такой, чтобы он нашёл кратчайший путь от конечной до начальной точки. Новичок в программировании, а скоро курсовую сдавать
Yandex
Объявления
30.11.2016, 17:52     Выкладываю реализацию алгоритма Дейкстры на С++
Ответ Создать тему
Опции темы

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