Графы

@White Luna · Регистрация: 08.09.2010

Студворк — интернет-сервис помощи студентам

Задача:
По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км.

Я думаю, что тут надо использовать ориентируемые графы.
Почитала литературу, и google но конкретно как описываются графы не нашла, подскажите кто что может, хоя бы с чего тут можно начать

@White Luna · 13.12.2010, 19:22 **[ТС]**

я начала как бы делать и советовалась с преподом, он сказал что готовая матр вводится как текстовый файл. и советовал использовать алгоритм Флойда-Уоршелла
Алгоритм Флойда - Уоршелла

Добавлено через 2 минуты
а можешь показать реализацию проги а то у ми после ввода данных вышибало, точнее после ввода последнего веса

@Mr.X · 14.12.2010, 15:17

Решение с помощью алгоритма Флойда-Уоршелла:

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
//////////////////////////////////////////////////////////////////////////////////////
//По системе односторонних дорог определить, есть ли в ней город, из которого 
//можно добраться до каждого из остальных городов, проезжая не более 100 км.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                    T_str;
typedef T_str                          T_vertice;
typedef std::set<T_vertice>            T_vertices_set;
typedef std::vector<T_vertice>         T_vertices;
typedef T_vertices                     T_arc;
typedef std::set<T_arc>                T_arcs_set;
typedef int                            T_weight;
typedef std::map<T_arc, T_weight>      T_arcs_weights;
typedef std::map<T_vertice, T_weight>  T_row;
typedef T_row::value_type              T_vert_weight;
typedef std::map<T_vertice, T_row>     T_adjacency_matr;
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr
    (
        const T_adjacency_matr&  matr,
        const T_weight           INFINITE_WEIGHT,
        const T_str              INFINITY_NAME
    )
{  
    for(T_adjacency_matr::const_iterator  vert_row_it = matr.begin(); 
        vert_row_it != matr.end(); ++vert_row_it)
    {
        for(T_row::const_iterator  vert_weight_it = vert_row_it->second.begin();
            vert_weight_it != vert_row_it->second.end(); ++vert_weight_it)
        {
            if(vert_weight_it->second == INFINITE_WEIGHT)
            {
                std::cout << '\t'
                          << INFINITY_NAME;
            }
            else
            {
                std::cout << '\t'
                          << vert_weight_it->second;
            }
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_arcs_set&  arcs_set)
{
    T_vertices_set  vertices_set;
    for(T_arcs_set::const_iterator  arc_it = arcs_set.begin(); arc_it != arcs_set.end();
        ++ arc_it)
    {
        vertices_set.insert(arc_it->front());
        vertices_set.insert(arc_it->back());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  get_adjacency_matr
    (
        const T_vertices&      vertices, 
        const T_arcs_weights&  arcs_weights,
        const T_weight         INFINITE_WEIGHT
    )
{
    T_adjacency_matr  adjacency_matr;
    for(T_vertices::const_iterator  vert_i_it = vertices.begin();
        vert_i_it != vertices.end(); ++vert_i_it)
    {
        for(T_vertices::const_iterator  vert_j_it = vertices.begin();
            vert_j_it != vertices.end(); ++vert_j_it)
        {
            adjacency_matr[*vert_i_it][*vert_j_it] = INFINITE_WEIGHT;
        }
    }
 
    for(T_arcs_weights::const_iterator   arc_weigh_it = arcs_weights.begin(); 
        arc_weigh_it != arcs_weights.end(); ++arc_weigh_it)
    {
        adjacency_matr[arc_weigh_it->first.front()]
                      [arc_weigh_it->first.back() ] = arc_weigh_it->second;
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  floyd_warshall
    (
        const T_vertices&        vertices,
        const T_adjacency_matr&  adjacency_matr,
        const T_weight           INFINITE_WEIGHT        
    )
{
    T_adjacency_matr D = adjacency_matr;
    //Обнуляем диагональные элементы.
    for(T_vertices::const_iterator  vert_i_it = vertices.begin();
        vert_i_it != vertices.end(); ++vert_i_it)
    {
        D[*vert_i_it][*vert_i_it] = T_weight();
    }
 
    for(T_vertices::const_iterator  vert_k_it = vertices.begin();
        vert_k_it != vertices.end(); ++vert_k_it)
    {
        for(T_vertices::const_iterator  vert_i_it = vertices.begin();
            vert_i_it != vertices.end(); ++vert_i_it)
        {
            for(T_vertices::const_iterator  vert_j_it = vertices.begin();
                vert_j_it != vertices.end(); ++vert_j_it)
            {
                if(   D[*vert_i_it][*vert_k_it] != INFINITE_WEIGHT
                   && D[*vert_k_it][*vert_j_it] != INFINITE_WEIGHT)
                {
                    D[*vert_i_it][*vert_j_it] 
                        = std::min(D[*vert_i_it][*vert_j_it],
                                   D[*vert_i_it][*vert_k_it] + D[*vert_k_it][*vert_j_it]);                
                }
            }        
        }    
    }
    return  D;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_vertices_distant_not_further_than
    (
        const T_weight           path_weight_max,
        const T_vertices&        vertices,
        const T_adjacency_matr&  adjacency_matr,
        const T_weight           INFINITE_WEIGHT,
        const T_str              INFINITY_NAME
    )
{    
    T_adjacency_matr  D(floyd_warshall(vertices, adjacency_matr, INFINITE_WEIGHT));    
    //Очевидно, что город, из которого можно добраться до каждого из остальных городов, 
    //проехав не более path_weight_max километров, имеет в матрице D минимальных длин путей 
    //между вершинами максимальный элемент в своей строке не больший, чем path_weight_max.
 
    T_vertices  res_vertices;
 
    struct  T_weight_compare
    {        
        bool  operator() (T_vert_weight  vert_weight_A, T_vert_weight  vert_weight_B)
        {
            return  vert_weight_A.second < vert_weight_B.second;
        }
    };
 
    for(T_adjacency_matr::const_iterator  D_vert_row_it = D.begin();
        D_vert_row_it != D.end(); ++D_vert_row_it)
    {
        T_row::const_iterator  vert_weight_max_it 
            = std::max_element(D_vert_row_it->second.begin(), D_vert_row_it->second.end(),
                               T_weight_compare());
 
        if(vert_weight_max_it->second <= path_weight_max)
        {
            res_vertices.push_back(D_vert_row_it->first);
        }    
    }
 
    std::cout << std::endl
              << "Матрица кратчайших путей межу городами:"
              << std::endl;
    print_matr(D, INFINITE_WEIGHT, INFINITY_NAME);
 
    if(res_vertices.empty())
    {
        std::cout << "В данной системе дорог нет города, из которого можно добраться "
                  << std::endl
                  << "до каждого из остальных городов, проехав не более "
                  << path_weight_max 
                  << " км."
                  << std::endl;
    }
    else
    {
        std::cout << "В данной системе дорог существует "
                  << res_vertices.size()
                  << " городов, "
                  << std::endl
                  <<"из которых можно добраться до каждого из остальных городов, "
                  << std::endl
                  << "проехав не более "
                  << path_weight_max 
                  << " км: "
                  << std::endl;    
 
        std::copy(res_vertices.begin(), res_vertices.end(), 
                  std::ostream_iterator<T_vertice>(std::cout, " "));
        std::cout << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n = 0;
    do
    {
        std::cout << "Введите количество дуг ориентированного взвешенного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
    T_arcs_set      arcs_set;
    T_arcs_weights  arcs_weights;
    const T_weight  INFINITE_WEIGHT = std::numeric_limits<T_weight>::max();
    const T_str     INFINITY_NAME = "INF";
    std::cout << "Введите "
              << n
              << " дуг ориентированного взвешенного графа."
              << std::endl
              <<"Вершины в дуге не должны быть одинаковыми.";
    do
    {
        std::cout << std::endl
                  << "дуга #"
                  << arcs_set.size() + 1
                  << ":"
                  << std::endl
                  << '\t'
                  << "начало: ";
        T_vertice  v1;
        std::cin >> v1;
        T_arc  arc_cur;
        arc_cur.push_back(v1);
        
        T_vertice  v2;
        std::cout << '\t'
                  << "конец : ";
        std::cin >> v2;        
        arc_cur.push_back(v2);        
        if(   arc_cur.size() == 2
           && arc_cur.front() != arc_cur.back())
        {
            if(arcs_set.insert(arc_cur).second)
            {
                T_weight  arc_weight;
                do
                {
                    std::cout << '\t'
                              << '\t'
                              << "вес >= 0"                              
                              << ": ";
                    std::cin >> arc_weight;
                }while(arc_weight < 0 || INFINITE_WEIGHT <= arc_weight);
                arcs_weights[arc_cur] = arc_weight;
            }
        }        
    }while(static_cast<int>(arcs_set.size()) < n);
 
    T_vertices  vertices = get_vertices(arcs_set);
 
    T_adjacency_matr  adjacency_matr 
        = get_adjacency_matr(vertices, arcs_weights, INFINITE_WEIGHT);
 
    std::cout << std::endl
              << "Матрица смежности графа ("
              << INFINITY_NAME 
              << " означает бесконечность):"
              << std::endl;
 
    print_matr(adjacency_matr, INFINITE_WEIGHT, INFINITY_NAME);
 
    std::cout << "Вершины графа:"
              << std::endl
              << '\t';
 
    std::copy(vertices.begin(), vertices.end(), 
              std::ostream_iterator<T_vertice>(std::cout, "\t"));
    std::cout << std::endl;
    
    const T_weight  path_weight_max = 100;
    
    print_vertices_distant_not_further_than
        (
            path_weight_max,
            vertices,
            adjacency_matr,
            INFINITE_WEIGHT,
            INFINITY_NAME
        );   
}

@White Luna · 14.12.2010, 17:45 **[ТС]**

Спасибо, но все таки свое написала в итоге, кому интересно то вот тут использовала другой алгоритм форда-беллмана, т к в том тока сама запуталась больше, вот
Всем спасибо за участие

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "iostream"
 
#define P 60
#define MAX 1000    //машинный эквивалент бесконечности
 
using namespace std;
 
int m[P][P];    // матрица для вычисления кратчайшего пути и его длины
int D[P], G[P][P], W[P][P],Z[P];
int N,M,S,F;
int a,b,c, w=0;
int i,j,k,l,h,f;
 
void GRAF (int m[P][P])     // функция нахождения кратчайшего пути
{        
for (i=1; i<=N; i++ )
    D[i] = m[S][i];     // массив , содержащий расстояния от заданной вершины до всех остальных 
    D[S] = 0 ;
for (j=1; j<=2 ; j++)   // матрица , хранящая путь из заданной вершины до всех остальных  
   {        
    G[j][1]=S;
    G[S][j]=0;
   }
for (h=1; h<=N; h++)    // Алгоритм Форда-Беллмана 
    {
     i=0;
    for (j=2; j<=N; j++) 
    {
     for (k=1; k<=N; k++) 
     {
      if (D[k] > D[j]+m[j][k])
        D[k]=D[j]+m[j][k];
        i++;
      for (l=2; l<=N; l++) 
      {
        W[i][l]=D[l];       // преобразуем для удобства массив расстояний в матрицу  (i-ая строка матрицы - массив расстояний на i-ом шаге )
        if (W[i][l]<W[i-1][l])      // отслеживаем улучшение пути
         G[k][2]=j;     // запоминаем вершину через которую проходит этот путь
      }
     }
    }
   }
     printf("\n");
  if (D[F]<MAX)     // если путь существует , то ...
  {                                        
    printf("\n длина пути от города %d  до остальных %d городов = \n",S,F);
    w=0;
    for(i=1; i<(F+1); i++)
     {
      cout << S;
      cout << "от";
      cout << i;
      cout << " ";
      printf("%d \n",D[i]);   // выводим длину пути 
 
      if(w<=D[i]) w=D[i];
      if (w==1000) w=D[i-1];
     }
    
    printf (" \n Максимальная длина пути от данного города = ");
if (w==1000) cout << "пути нету!!!, данный город конечный";
    else cout << w;
         cout << "\n";
if(w<=6)
{
  cout<< " \n Из города ";
  cout <<S;
  cout << "  можно! добраться до каждого из остальных городов, проезжая не более 100 км.\n";
}
   else
   {
    cout <<" \n Из города ";
    cout <<S;
    cout <<"  !!нельзя!! добраться до каждого из остальных городов, проезжая не более 100 км. \n";}
   }
 
for(int as=1; as<(F+1); as++)
 {
  printf(" \n путь между %d u %d городами  : ",S,as);
 if (D[as]<MAX)     // если путь существует , то ...
 {                                       
    i=1;
    Z[0]=as;
    while (G[as][2] !=0)    // в массив Z записываем вершины , через которые проходит путь , в обратном порядке (от конечной к начальной вершине)
    {
     Z[i]=G[as][2];
     i++;
     G[as][2]=G[G[as][2]][2];
    }
     Z[i]=S;
    for (j=i ; j>=0 ;j--)
    printf(" %d",Z[j]);     // выводим вершины , через которые проходит путь , в правильном порядке
  }
   else   // если пути нет , то ...
   {
     printf("пути нет!");                 
   };
 }
}
 
int main () 
{
 setlocale (LC_ALL, "Russian");
 char fileName[256];
  FILE *inp;
   inp=fopen("text.txt", "r");      // открываем файл на чтение
   fscanf (inp,"%d %d",&N,&M);      // Читаем из файла первую строку, cодержащую число вершин N и число ребер M
 
   for ( i=1 ; i<=N ; i++)          // присваиваем элементам обоих матриц максимальные значения 
   {
    for ( j=1 ; j<=N ; j++) 
    {
     m[i][j]=MAX;
    }
   }
   for (i=1 ;i<=M ;i++ )            // Читаем из файла остальные M строк , 
   {
    fscanf(inp,"%d %d %d",&a,&b,&c);     // содержащие описание ребер (Пример строки файла :" 1 3 6 ": значит, что ребро из вершины 1 в вершину 3 имеет вес 6)  
    m[a][b]=c;                      // Заполняем матрицу смежностей для нашего графа , учитывая вес рёбер
   }
   fclose(inp);                     // закрываем файл
    printf("\n");
   int q=1;
   do{
      for (S=1; S<=N; S++)
       {
        F=7;
        GRAF(m);
        cout << "\n";   
        }
      printf ("Хотите повторить запрос нажмите 1, выйти нажмите 0 \n");
      scanf_s ("%d", &q);
     }
   while (q==1);
 
 system ("\n pause");
 exit (0);
 getch();
 return 0 ;
}

Новые блоги и статьи Все статьи Все блоги /
Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .

@White Luna 33 / 27 / 2 Регистрация: 08.09.2010 Сообщений: 402

	Графы 05.12.2010, 14:30. Показов 5643. Ответов 22 Метки нет (Все метки) Задача: По системе односторонних дорог определить, есть ли в ней город, из которого можно добраться до каждого из остальных городов, проезжая не более 100 км. Я думаю, что тут надо использовать ориентируемые графы. Почитала литературу, и google но конкретно как описываются графы не нашла, подскажите кто что может, хоя бы с чего тут можно начать 0

@White Luna 33 / 27 / 2 Регистрация: 08.09.2010 Сообщений: 402
	13.12.2010, 19:22 [ТС]
	я начала как бы делать и советовалась с преподом, он сказал что готовая матр вводится как текстовый файл. и советовал использовать алгоритм Флойда-Уоршелла Алгоритм Флойда - Уоршелла Добавлено через 2 минуты а можешь показать реализацию проги а то у ми после ввода данных вышибало, точнее после ввода последнего веса 0