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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 158, средняя оценка - 4.77
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
#1

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

18.12.2011, 01:26. Просмотров 21310. Ответов 16
Метки нет (Все метки)

Добрый вечер! Помогите решить задание пожалуйста: написать программу, решающую задачу в соответствие с вариантом, и вывести результат графически на экран.
Найти кратчайшие пути из точки M1 в точку M9
Миниатюры
Поиск кратчайшего пути в графе  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2011, 01:26     Поиск кратчайшего пути в графе
Посмотрите здесь:

C++ Поиск оптимального пути в графе
C++ Поиск кратчайшего пути на клетчатом поле.
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Восстановление кратчайшего пути в графе C++
C++ Поиск кратчайшего пути в матрице через рекурсию
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 11:06  [ТС]     Поиск кратчайшего пути в графе #2
Я смотрел разные варианты программ здесь, но похожего не видел, больше всего смущает графическое решение... Помогите пожалуйста

Добавлено через 9 часов 40 минут
Ну помогите а?
Dani
1264 / 622 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 11:15     Поиск кратчайшего пути в графе #3
Флойд, Дейкстра или Форд-Беллман. Надо только матрицу смежности построить.

Добавлено через 57 секунд
Дейкстра
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
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
   //**********************************************************************
    int a[500][500],d[500]={0},n,s,f,flag[500],l,min1=100000000,nmin=0;
    for (int i=0;i<=500;i++) flag[i]=1;
    std:: ifstream ifs ("input.txt");
    ifs >> n >> s >> f;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)//ввод
    {
     ifs >> a[i][j];
     if (a[i][j]==-1 && i!=j) a[i][j]=32000;
    }
    ifs.close();
    //*********************************************************************
    l=s;
    for (int i=1;i<=n;i++) d[i]=a[l][i];//задание начальных значений массиву d
    flag[l]=0;
    
    for (int i=1;i<=n-1;i++)
    {
        min1=100000000;
        nmin=l;
        for (int j=1;j<=n;j++)
        if (flag[j]!=0 && min1>d[j]) 
        { 
           min1=d[j]; 
           nmin=j; 
        } // ищем ближайшую вершину
        
        l=nmin;
        
        flag[l]=0;
        
        for (int j=1;j<=n;j++)
        if (flag[j]!=0) 
        d[j]=std:: min (d[j],a[l][j]+d[l]); //минимальное расстояние до d[j]
        
    }
    
    
    std:: ofstream ofs ("output.txt");
    if (d[f]==32000) ofs << "-1";
    else ofs << d[f];
    ofs.close();
    return 0;
}


Флойд
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
#include <fstream>
#include <algorithm>
int main()
{
    int n, a[101][101];
    std:: ifstream ifs ("input.txt");
    ifs >> n;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    ifs >> a[i][j];
    ifs.close();
    for (int k=1;k<=n;k++)
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    a[i][j]=std:: min (a[i][j],a[i][k]+a[k][j]);
    std:: ofstream ofs ("output.txt");
    for (int i=1;i<=n;i++)
    {
      for (int j=1;j<=n;j++)
      ofs << a[i][j] << " ";
      ofs << '\n';
    }
    ofs.close();
    return 0;
}


Добавлено через 2 минуты
А графику уже достроите
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 20:42  [ТС]     Поиск кратчайшего пути в графе #4
Я как раз и не знаю как графически вывести ответ, и с матрицей смежности тоже не пойму что делать...

Добавлено через 55 минут
Готов заплатить через Яндекс деньги! Только помогите, завтра сдать надо эту штуку... Еще бы блоксхему бы...

Добавлено через 28 минут
неужели никто не возьмется? 300-450 рублей заплачу за задачу и блоксхему...

Добавлено через 1 час 7 минут
ну возмитесь кто нибудь, завтра сдавать нужно, а я вообще в непонятках как делать
dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
18.12.2011, 20:51     Поиск кратчайшего пути в графе #5
У меня маленький вопрос, какой алгоритм быстрее Дейкстры или Флойда?
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 20:53  [ТС]     Поиск кратчайшего пути в графе #6
У нас все делают через Дейкстра.
dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
18.12.2011, 20:58     Поиск кратчайшего пути в графе #7
да я тоже про Дейкстру много инфы находил, про Флойда в первый раз услышал но реализация очень понравилась.
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 21:18  [ТС]     Поиск кратчайшего пути в графе #8
Ну как сделать то мое задание знает кто нибудь? Плачу 400 р. (прога и блоксхема)

Добавлено через 18 минут
А все, не надо, кажется я все сделал)))
Dani
1264 / 622 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 21:41     Поиск кратчайшего пути в графе #9
Цитата Сообщение от aram_gyumri Посмотреть сообщение
Дейкстры или Флойда?
Флойд N^3
Дейкстра N^2
Дейкстра с кучей N*logN

Добавлено через 40 секунд
Иначе не было бы смысла в Дейкстре писать 20 строк, чем во Флойде 3
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 21:44  [ТС]     Поиск кратчайшего пути в графе #10
Народ, подойдет код для моего задания:

Код
//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused

#define VERTEXES 9	//Число вершин в графе

int v;
int main(int argc, char* argv[])
{
   clrscr();
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;				// Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
     	                         0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };

   // Будем искать путь из вершины s в вершину g
   int s;              		// Номер исходной вершины
   int g;              		// Номер конечной вершины
   cout<<"Введите s: ";  	// Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
   		         // на кратчайшем пути

   // Инициализируем начальные значения массивов
   int u;		    // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; //Сначала все кратчайшие пути из s в i 
	//равны бесконечности
      x[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь
   v=s;    // Делаем s текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не 
	//найден кратчайший путь
            	// и новый путь в u короче чем 
	//старый, то
         {
            t[u]=t[v]+a[v][u];	//запоминаем более короткую длину пути в
	//массив t и
            h[u]=v;	//запоминаем, что v->u часть кратчайшего 
	//пути из s->u
         }
      }

      // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший 
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) // Найден кратчайший путь,
      {        // выводим его
         cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
   	   u=g;
   	   while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". Длина пути - "<<t[g];
   	   break;
      }
      x[v]=1;
   }
   getch();
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 

Нет пути из вершины 3 в вершину 6. 

После ввода s = 0, q = 2 программа выводит 

Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/

//---------------------------------------------------------------------------

Подойдет это?
Dani
1264 / 622 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 21:46     Поиск кратчайшего пути в графе #11
Цитата Сообщение от bacekk Посмотреть сообщение
и вывести результат графически на экран.
...
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 21:50  [ТС]     Поиск кратчайшего пути в графе #12
Можно и без графического вывода оказывается.
Не компилится, пишет: Unable to open include file 'VCL.H'
как исправить?
Dani
1264 / 622 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.12.2011, 21:50     Поиск кратчайшего пути в графе #13
убрать нафиг
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
19.12.2011, 02:02  [ТС]     Поиск кратчайшего пути в графе #14
А как будет выглядить матрица смежности для графа?

Добавлено через 3 часа 46 минут
Можете мне написать матрицу смежности для моего графа, пожалуйста...
Я так понял что она будет 9x9 и ставится 1 если из одной точки можно попасть в другую, а если нельзя то 0...
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
19.12.2011, 08:25     Поиск кратчайшего пути в графе #15
вроде так:
0 1 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 0 0
0 0 1 0 0 1 1 0 1
0 0 1 0 0 1 1 1 0
0 1 0 1 1 0 0 0 0
0 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 1
0 0 0 1 0 0 1 1 0
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
21.12.2011, 16:57  [ТС]     Поиск кратчайшего пути в графе #16
Народ, может вопрос не совсем по теме. Меня интересует как работает алгоритм Дейкстра на этом примере, я просто защищаю лабу уже второй раз подряд, заваливаюсь на одном и том же.
Вот как я ему объясняю: все расстояния между вершинами в начале равны бесконечности, начинаем из вершины м1, так как ей ничего не предшествует, кратчайший путь из м1 в м1 равен 0, потом идем дальше к вершине м2, записываем для нее расстояние от м1, допустим 1, и запоминаем для нее кратчайший путь. Далее из вершины м2 мы можем попасть в м3 или м6, идем в м3, так как логичнее сначала туда пойти, запоминаем расстояние и путь для нее, дальше у нас выбор между м5 и м4, идем в м4, запоминаем расстояние и путь для нее. а вот дальше все что бы я не говорил, он не воспринимал, и говорил, что все неправильно... Можете подсказать каким образом проходит алгоритм Дейкстра в этом графе и как мне все это преподу рассказать по шагам. Заранее спасибо)

Добавлено через 15 часов 0 минут
Ответьте, кто-нибудь..
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2013, 14:21     Поиск кратчайшего пути в графе
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Михалин17
5 / 5 / 1
Регистрация: 03.04.2013
Сообщений: 46
12.04.2013, 14:21     Поиск кратчайшего пути в графе #17
а как такое на visual basice 2005 сделать?
Yandex
Объявления
12.04.2013, 14:21     Поиск кратчайшего пути в графе
Ответ Создать тему
Опции темы

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