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

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

Войти
Регистрация
Восстановить пароль
 
maximuss
0 / 0 / 0
Регистрация: 24.04.2012
Сообщений: 148
#1

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

26.05.2014, 08:50. Просмотров 273. Ответов 0
Метки нет (Все метки)

Помогите изменить задачу :
Есть : 1) Вводим кол-во узлов, вводим длину между точками - выводит результат..

Нужно : 1) Водим кол-во узлов, потом вводим значение между узлами. (1- пинг, 2 - скорость, 3 - загруженность, 4 - длина). Потом выбираем поиск за такими параметрами (один из 4-ех): 1) Пинг
2) Скорость
3)Загруженность
4) Длина
(Примеч:Поиск кратчайшего пути по пингу, загруженности и длине - чем меньше, тем и оптимальнее. По скорости, чем больше тем и лучше.)
Как результат, нужно, что бы вывело весь путь(Прим. х1-х2-х5-х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
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
121
122
123
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 #include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define word unsigned int
 
//---------------------------------------------------------------------------
 
#pragma argsused
 
 
 
 
int i, j, n, p, xn, xk;
int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
int min(int n)
{
 int i, result;
for(i=0;i<n;i++)
if(!(flag[i])) result=i;
for(i=0;i<n;i++)
if((l[result]>l[i])&&(!flag[i])) result=i;
return result;
}
word minim(word x, word y)
{
if(x<y) return x;
return y;
}
void main()
{
cout<<"Vvedit` kil`kist` tochok: ";
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++) c[i][j]=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
cout<<"Vvedit` vidstan` vid x"<<i+1<<" do x"<<j+1<<": ";
cin>>c[i][j];
}
cout<<" ";
for(i=0;i<n;i++) cout<<" X"<<i+1;
cout<<endl<<endl;
for(i=0;i<n;i++)
{
printf("X%d",i+1);
for(j=0;j<n;j++)
{
printf("%6d",c[i][j]);
c[j][i]=c[i][j];
}
printf("\n\n");
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(c[i][j]==0) c[i][j]=65535; //безкінечнність
cout<<"Vvedit` pochatkovi tochku: ";
cin>>xn;
cout<<"Vvedit` kincevi tochku: ";
cin>>xk;
xk--;
xn--;
if(xn==xk)
{
cout<<"Pochatkova i kinceva tochku spivpadayut`."<<endl;
getch();
return;
}
for(i=0;i<n;i++)
{
flag[i]=0;
l[i]=65535;
}
l[xn]=0;
flag[xn]=1;
p=xn;
itoa(xn+1,s,10);
for(i=1;i<=n;i++)
{
strcpy(path[i],"X");
strcat(path[i],s);
}
do
{
for(i=0;i<n;i++)
if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
{
if(l[i]>l[p]+c[p][i])
{
itoa(i+1,s,10);
strcpy(path[i+1],path[p+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
l[i]=minim(l[i],l[p]+c[p][i]);
}
p=min(n);
flag[p]=1;
}
while(p!=xk);
if(l[p]!=65535)
{
cout<<"Shljah: "<<path[p+1]<<endl;
cout<<"Dovjuna shljahy: "<<l[p]<<endl;
}
else
cout<<"takogo shljahy ne isnye!"<<endl;
getch();
 
 
 
 }
 
 
//---------------------------------------------------------------------------
Добавлено через 16 часов 46 минут
ап(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2014, 08:50     Поиск кратчайшего пути в графе
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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