Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 04.02.2015
Сообщений: 19

Задача на взвешенный ориентированный граф, существует ли путь L между двумя заданными вершинами

13.10.2019, 18:18. Показов 1587. Ответов 6

Студворк — интернет-сервис помощи студентам
Во входном файле указывается количество вершин взвешенного ориентированного графа и матрица смежности. Определить, существует ли путь длинной L между двумя данными вершинами.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.10.2019, 18:18
Ответы с готовыми решениями:

В неориентированном графе требуется найти минимальный путь между двумя вершинами
Путь В неориентированном графе требуется найти минимальный путь между двумя вершинами. Входные данные Во входном...

Найти кратчайший путь между двумя заданными городами
Дана плоская страна и в ней n городов. Предположим, что в этой стране есть дорожная сеть. Найти кратчайший путь между двумя заданными...

Граф задан матрицей смежности. Определите, существует ли в графе путь между двумя заданными вершинами(в делфи).
Помогите пожалуйста с Задачей, как ни пробовала - не получается... Граф задан матрицей смежности. Определите, существует ли в графе путь...

6
58 / 42 / 21
Регистрация: 01.01.2018
Сообщений: 273
13.10.2019, 22:14
А в чем загвоздка? Матрица смежности - массив, в котором надо сравнить L с элементом с индексами [1ая верш., 2ая верш.]. Совпали значения? - Прекрасно, ответ на задачу - да, путь существует. Иначе - нет

Добавлено через 15 минут
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var point1, point2, L, vertAmount:integer;
  t:text;
 
begin
  assign(t, 'task.txt');
  t.Reset;
  L:=t.ReadInteger;
  vertAmount:=t.ReadInteger;
  point1:=t.ReadInteger;
  point2:=t.ReadlnInteger;
  
  for var i:integer:=2 to point1 do t.Readln;
  for var i:integer:=2 to point2 do t.ReadInteger;
  if t.ReadInteger = L then println('Существует') else println('Не сущестует');
end.
Текстовик:
Pascal
1
2
3
4
5 3 2 1
2 3 1
5 4 3
2 3 0
1
0 / 0 / 0
Регистрация: 04.02.2015
Сообщений: 19
15.10.2019, 08:01  [ТС]
Цитата Сообщение от Ksardas_178 Посмотреть сообщение
А в чем загвоздка? Матрица смежности - массив, в котором надо сравнить L с элементом с индексами [1ая верш., 2ая верш.]. Совпали значения? - Прекрасно, ответ на задачу - да, путь существует. Иначе - нет
А такой метод разве проверяет все возможные пути? Допустим, нам нужно узнать, есть ли путь длиной в 5 между вершинами 1 и 3. Прямой путь такая программа проверит, а путь 1-2-3, проходящий через вершину 2, нет. Ведь там в сумме тоже может быть 5. 1-2 длиной в 2, и 2-3 длиной в 3. Насколько я понял, здесь нужно строить граф и обходить его, только потом прикручивать проверку. Но как, я не знаю
0
58 / 42 / 21
Регистрация: 01.01.2018
Сообщений: 273
15.10.2019, 13:31
Искал прямой путь. Если к вечеру не решат, напишу обход
0
58 / 42 / 21
Регистрация: 01.01.2018
Сообщений: 273
16.10.2019, 00:53
Обходим по всем направлениям, считая те, откуда пришли. Ограничение только на длину оставляем. Программа выводит пути в виде точек, индексация с нуля.

Pascal
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
var
  point1, point2, L, vertAmount: Integer;
  t: text;
  paths: array of array of Integer;
 
procedure findPath(point, length: Integer; path: LinkedList<Integer>);
begin
  path.AddLast(point);
  if (length = L) and (point = point2) then println(path);
  if length < L then
    for var j := 0 to vertAmount - 1 do 
      if (paths[point, j] > 0) then findPath(j, length + paths[point, j], new LinkedList<Integer>(path));
end;
 
begin
  assign(t, 'task.txt');
  t.Reset;
  L := t.ReadInteger;
  vertAmount := t.ReadInteger;
  point1 := t.ReadInteger;
  point2 := t.ReadlnInteger;
  
  setLength(paths, vertAmount);
  for var i := 0 to (vertAmount - 1) do
  begin
    setLength(paths[i], vertAmount);
    for var j := 0 to (vertAmount - 1) do paths[i, j] := t.ReadInteger;
    t.Readln;
  end;
  t.Close;
  findPath(point1, 0, new LinkedList<Integer>)
end.
txt:
Pascal
1
2
3
4
5
5 4 0 2
0 3 4 1
0 0 2 0
0 0 1 0
0 2 1 0
Добавлено через 5 минут
ЗЫ: Вместо LinkedList<> вполне сойдет и List<> (List.Add(point)) соответственно
0
0 / 0 / 0
Регистрация: 04.02.2015
Сообщений: 19
17.10.2019, 10:53  [ТС]
Цитата Сообщение от Ksardas_178 Посмотреть сообщение
Обходим по всем направлениям, считая те, откуда пришли. Ограничение только на длину оставляем. Программа выводит пути в виде точек, индексация с нуля.
А можете объяснить, что именно идет на вывод? Это строчки со всеми длинами путей, которые идут до каждой из вершин? И еще, что такое vertAmount?
0
58 / 42 / 21
Регистрация: 01.01.2018
Сообщений: 273
17.10.2019, 14:32
Ruslan_64, на вывод идут последовательности вершин, через которые проходит искомый путь. vertAmount - vertex amount, количество вершин графа.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.10.2019, 14:32
Помогаю со студенческими работами здесь

Граф - существует ли связь между двумя вершинами в обоих направлениях
В файле задан ориентированный граф. В первой строчке записано число N, которое обозначает кол-во вершин в графе. Во второй строчке записано...

Граф - существует ли связь между двумя вершинами в обоих направлениях
В файле задан ориентированный граф. В первой строчке записано число N, которое обозначает кол-во вершин в графе. Во второй строчке записано...

Граф - существует ли связь между двумя вершинами в обоих направлениях
В файле задан ориентированный граф. В первой строчке записано число N, которое обозначает кол-во вершин в графе. Во второй строчке записано...

Существует ли путь между двумя вершинами графа
Текст задачи: &quot;Граф задан с помощью цепных списков. Определить, существует ли путь между двумя заданными вершинами.&quot; Так как...

Существует ли путь между двумя вершинами графа
Задача звучит так: &quot;Граф задан с помощью цепных списков. Определить, существует ли путь между двумя заданными вершинами.&quot; Я...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru