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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Стрелки совершают N выстрелов из пистолета по мишени. Кучность стрельбы может быть описана суммой квадратов отклонений результатов каждого выстрела от http://www.cyberforum.ru/cpp-beginners/thread226022.html
Спасибо :)) Ещё пару задач. Стрелки совершают N выстрелов из пистолета по мишени. Кучность стрельбы может быть описана суммой квадратов отклонений результатов каждого выстрела от среднего значения. Определить кто из двух стрелков стрелял кучнее, если их баллы {6,9,3,10,10,3,10,9,6,10} и {6,4,7,7,6,8,7,4,6,6}. И вторая. Сотрудник ГАИ замеряет скорость движения автомашин по трассе. Определить...
C++ Можно ли создать процесс(CreateProcessWithLogonW) на удаленном компьютере? Добрый день. Можно ли создать процесс на удаленном компьютере зная ip, пароль и имя пользователя. На подобии функций: CreateProcessWithLogon() CreateProcess() чтобы запустить там cmd.exe и перенаправить его поток вывода в переменную? http://www.cyberforum.ru/cpp-beginners/thread226018.html
C++ WinAPI OpenDialog, получить имя открытого файла
Всем добрый день. Не получается получить имя открытого файла в OpenDialog. OPENFILENAME ofn; LPSTR openedfile; ... void InitOpenDialog()
C++ полиморфизм
Всем привет, изучаю С++ недавно, я новичек в этом языке программирования, читаю про ООП, понял все за исключением полиморфизма, что делает оператор virtual зачем вообще нужен полиморфизм и еще не понял вот этот код #include <iostream> #include <cstdlib> #include <cstdio> #include <string> class Student { public: Student* makecopy() { // тут функция копии
C++ начало и конец цикла в коде. http://www.cyberforum.ru/cpp-beginners/thread225959.html
Вот программа по определению магического квадрата из матрицы, заданной в txt файле. #include "stdafx.h" #include <iostream> #include <fstream> #include <cmath> using namespace std; int main() { const int z=3; int q,A, i,j,e,r=1, stolb=0, strok,stro, stol, diag1=0, diag2=0, t, o,k; // diag1- побочная диагональ fstream(fin);
C++ Builder Медиапроигрыватель Скажите пожалуста первый день осваиваю С++ в среде редактора Builder 6 . Занимаюсь по видео урокам, там на примере показывается создание простейшего проигрывателя в Builder 6, но почему то редактор выдает ошибку в коде в этой строке if (OpenDialog1->Execute()) MediaPlayer1->FileName=OpenDialog1->FileName MediaPlayer1->Open(); вот весь код:... подробнее

Показать сообщение отдельно
abd256
8 / 8 / 0
Регистрация: 08.01.2011
Сообщений: 9
09.01.2011, 11:12     Выкладываю реализацию алгоритма Дейкстры на С++
Дпанная программа выполняет поиск по заданной матрице весов. Далее указываем начальную точку в графе и программа расчитывает все кратчайшие растояния от начальной точки до остальных следующим видом:путь от нач. точки до 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 минуту
Надеюсь людям понравится
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 01:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru