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

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

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

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

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

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

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

Поиск кратчайшего пути в графе - C++
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном ациклическом ориентированном графе с нагруженными ребрами. ...

Восстановление кратчайшего пути в графе - C++
Есть алгоритм нахождения кратчайших путей(Флойд), а как восстановить путь как узнать через какие вершины он прошел?туплю прогаю с утра)) ...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной - C++
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие...

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

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

Добавлено через 9 часов 40 минут
Ну помогите а?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 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 минуты
А графику уже достроите
2
bacekk
2 / 2 / 0
Регистрация: 30.11.2010
Сообщений: 89
18.12.2011, 20:42  [ТС] #4
Я как раз и не знаю как графически вывести ответ, и с матрицей смежности тоже не пойму что делать...

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

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

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

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

Добавлено через 40 секунд
Иначе не было бы смысла в Дейкстре писать 20 строк, чем во Флойде 3
1
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.*/

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

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

Добавлено через 3 часа 46 минут
Можете мне написать матрицу смежности для моего графа, пожалуйста...
Я так понял что она будет 9x9 и ставится 1 если из одной точки можно попасть в другую, а если нельзя то 0...
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
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2011, 08:25
Привет! Вот еще темы с ответами:

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

Нахождение кратчайшего пути, поиск с возвратом - C++
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...

Поиск кратчайшего пути на клетчатом поле. - C++
Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти...

Поиск кратчайшего пути в матрице через рекурсию - C++
Есть задача: найти кратчайший путь в матрице,представляющий из себя сумму значений ее элементов. Матрица размера 10х10. Я реализовал сам...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
19.12.2011, 08:25
Ответ Создать тему
Опции темы

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