Лабораторная №3
Поиск оптимальных путей в графе(6 часов)
Цель: Изучение основных алгоритмов поиска оптимальных путей в графе.
Задание:
1. Для неориентированного графа сохранить его в виде списка смежности.
2. Построить алгоритмы поиска кратчайших путей в графе (dfs, Флойда, Дейкстры, Дейкстры с кучей, Белмана-Форда)
Отчет должен содержать: Постановку задачи, графическую схему алгоритма. Для алгоритма Дейкстры и Белмана-Форда подробное описание порядка вычисления по шагам для теста из варианта задания. Отчет оформляется от руки за исключением текста и результатов программы.
Вариант 1,13.
Количество вершин 8 , количество связей 10.
1 -> 3
1 -> 5
2 -> 4
6 - > 8
7 -> 5
2 -> 8
8 -> 4
3 -> 5
Вариант 2,14.
Количество вершин 8 , количество связей 10.
2 -> 3
1 -> 5
2 -> 4
7 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 3, 15.
Количество вершин 8 , количество связей 10.
1-> 2
1 -> 5
2 -> 4
6- >3
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 4,16.
Количество вершин 8 , количество связей 10.
2 -> 8
1 -> 5
2 -> 1
3 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 5,17.
Количество вершин 8 , количество связей 10.
2 -> 6
1 -> 5
2 -> 1
3 - > 1
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 6,18.
Количество вершин 8 , количество связей 10.
4 -> 8
6 -> 5
2 -> 1
3 - > 8
7 -> 5
2 -> 8
8 -> 4
4 -> 5
Вариант 7,19.
Количество вершин 8 , количество связей 10.
1 -> 7
2 -> 5
2 -> 1
3 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 1
Вариант 8,20.
Количество вершин 8 , количество связей 10.
2 -> 8
4 -> 5
2 -> 1
3 - > 8
7 -> 5
7 -> 8
8 -> 4
6 -> 5
Вариант 9,21.
Количество вершин 8 , количество связей 10.
2 -> 8
1 -> 4
2 -> 6
3 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 10,22.
Количество вершин 8 , количество связей 10.
2 -> 7
3 -> 5
2 -> 1
1 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 11, 23.
Количество вершин 8 , количество связей 10.
3 -> 4
1 -> 5
2 -> 1
1 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 5
Вариант 12,24.
Количество вершин 8 , количество связей 10.
2 -> 8
1 -> 5
2 -> 1
3 - > 8
7 -> 5
2 -> 8
8 -> 4
6 -> 7
Задачи из сайта dl.gsu.by.(для желающих). Там их можно оттестировать.
|
Задачи для книги\Графы\Контрольные задачи\Г13 - "КРАТЧАЙШИЙ ПУТЬ" 21551 ??? |
Баллов: 100 в новом окне |
Задан связный неориентированный взвешенный граф G. В графе возможно наличие нескольких ребер между одной и той же парой вершин. Найдите вес кратчайшего пути между двумя заданными вершинами A и B.
Входные данные.
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 10000) - количество вершин графа. Вторая строка входного файла содержит целое число M (1 ≤ M ≤ 100000) - количество ребер графа. В каждой из следующих M строк содержатся ровно три числа a, b, c (1 ≤ a, b ≤ N, 1 ≤ c ≤ 100000). Эти числа описывают ребро, соединяющее вершины с номерами a и b и имеющее вес c. Последние две строки содержат целые числа A и B (1 ≤ A, B ≤ N) - начальную и конечную вершины пути. Вершины нумеруются последовательными натуральными числами от 1 до N.
Выходные данные. Единственная строка выходного файла должна содержать одно целое число, равное весу кратчайшего пути между вершинами A и B в графе G.
Пример.
|
input.txt |
output.txt |
|
3 3 1 2 3 1 3 1 2 3 1 1 2 |
Олимпиады по информатике\Скрытые и явные графы\BFS (Очередь)\07_Rub11 - "Ладья в лабиринте" 58245 ???
Задача Ладья в лабиринте
Ладья - это шахматная фигура, которая за один ход может переместиться на любое количество клеток по горизонтали или вертикали. При этом она не может "перепрыгивать" через стоящие на ее пути фигуры. Вася недавно соорудил на шахматной доске своеобразный лабиринт - в некоторые клетки доски он поставил пешки (самые "слабые" шахматные фигуры). Теперь он хочет знать, за какое минимальное количество ходов ладья может добраться из одной клетки в другую. Он размышляет над этим вопросом уже несколько дней, однако найти ответ не может. Поэтому он решил обратиться за помощью к Вам. Напишите программу, находящую ответ на Васину задачу.
Формат ввода:
Первая строка входного файла содержит два натуральных числа: n и m (1 <= n;m <= 500) размеры лабиринта. Каждая из последующих n строк содержит m символов. j-ый символ i-ой из этих строк соответствует клетке с координатами (i; j). Он равен "." (точка), если клетка пуста, P, если занята пешкой, S, если это начальная клетка для ладьи, F, если это конечная клетка.
Формат вывода:
В выходной файл выведите минимальное количество ходов, требуемое ладье для того, чтобы из начальной клетки попасть в конечную. Если конечная клетка недостижима из начальной выведите -1.
|
Пример ввода: |
Пример вывода: |
|
4 4 F.PS .PP. .PP. .... |
3 |
|
Пример ввода: |
Пример вывода: |
|
4 4 F.PS .PP. .PP. .P.. |
-1 |
|
USACO 2004-2011\Silver\Графы\АлгоритмДейкстраскучей\11_MarS - "Package Delivery" 103153 Damon Doucet, 2011 Англ. вариант |
Бал |
Problem 7: Package Delivery [Damon Doucet, 2011]
Фермер Джон должен передать пакет фермеру Дану. ФД должен дать вкусную
еду каждой корове, которую встретит по дороге, но в силу своей жадности,
он хочет встретить как можно меньше коров.
ФД нарисовал карту из N (1 <= N <= 50,000) амбаров, связанных M
(1 <= M <= 50,000) двунаправленными дорожками, с C_i коровами,
пасущимися на дорожке i. Дорожка I соединяет амбары A_i и B_i
(1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i). Два амбара могут быть
соединены более чем одной дорожкой. ФД находится в амбаре 1, а
фермер Дан – в амбаре N.
Для примера рассмотрим карту:
[2]---
/ | \
/1 | \ 6
/ | \
[1] 0| --[3]
\ | / \2
4\ | /4 [6]
\ | / /1
[4]-----[5]
3
Лучший путь для ФД - 1 -> 2 -> 4 -> 5 -> 6, поскольку он будет
вынужден давать пищу коровам 1 + 0 + 3 + 1 = 5 раз.
По карте ФД определите минимальное количество раз давать пищу
коровам (каждую корову кормить ровно один раз). ФД не должен
беспокоиться о длине своего пути.
PROBLEM NAME: packdel
INPUT FORMAT:
* Строка 1: Два разделенных пробелом целых числа: N M
* Строки 2..M+1: Три разделенных пробелами целых числа: A_i B_i C_i
SAMPLE INPUT (файл packdel.in):
6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4
OUTPUT FORMAT:
* Строка 1: Минимальное количество коров, которых ФД должен покормить.
SAMPLE OUTPUT (файл packdel.out):
5
USACO 2004-2011\Silver\Графы\АлгоритмБеллмана-Форда\09_NovS - "Job Hunt
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
