Не пропустите майские цены на инструменты учителя! Скидки до 50% на все комплекты видеоуроков и электронных тетрадей.

СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Выбрать материалы

Скидки до 50 % на комплекты
только до

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Была в сети 17.04.2024 23:50

Халяпова Наиля Миргарифановна

Учитель информатики

1 147

44 004

Подписчики

Подписки

Местоположение

Россия, Казань

Специализация

Информатика

Обо мне Блог Файлы Тесты Галерея Активность Награды

Алгоритм Дейкстры

Категория: Информатика

01.10.2019 23:21

Поиск кратчайшего пути алгоритмом Дейкстры на примере

Просмотр содержимого документа
«Алгоритм Дейкстры»

Задача.

Для взвешенного графа, заданного списком ребер, найти кратчайший путь между вершинами x и y, воспользовавшись алгоритмом Дейкстры. , .

Вершины ребра	1	1	2	2	3	3	4	5	5	6	6	7	7	7	8	10	10	5
Вершины ребра	2	5	3	6	4	7	8	6	9	7	9	4	8	10	10	9	5	10
Вес ребра	7	10	14	9	15	18	21	8	41	11	44	5	15	16	17	5	50	10

Решение.

По условиям таблицы данный взвешенный граф – ориентированный, так как вес ребра (10,5) равен 50, а вес ребра (5,10) равен 10.

Построим для хранения весов графа квадратную матрицу

	1	2	3	4	5	6	7	8	9	10
1		7			10
2			14			9
3				15			18
4								21
5						8			41	10
6							11		44
7				5				15		16
8										17
9
10					50				5

Проставим по главной диагонали нули, в пустые клетки первой строки знак "∞", который будет обозначать отсутствие пути из вершины 1 в соответствующую вершину, на которую указывает номер столбца.

	1	2	3	4	5	6	7	8	9	10
1	0	7	∞	∞	10	∞	∞	∞	∞	∞
2		0	14			9
3			0	15			18
4				0				21
5					0	8			41	10
6						0	11		44
7				5			0	15		16
8								0		17
9									0
10					50				5	0

Далее выделим из таблицы первую строку:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞

В первой строке минимальное значение равно 7. Выделим его жирным шрифтом.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞

Кратчайший путь длиной 7 ведет к вершине 2 из вершины 1. Далее смотрим, куда можно попасть из вершины 2. Из вершины 2 можно попасть в вершину 3, длина пути будет 7+14=21. Из вершины 2 можно попасть в вершину 6, длина пути будет 7+9=16. Запишем это в следующую строку таблицы:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞

В новой строке минимальное значение равно 10. Выделим его жирным шрифтом.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞

Кратчайший путь длиной 10 ведет к вершине 5 из вершины 1. Далее смотрим, куда можно попасть из вершины 5. Из вершины 5 можно попасть в вершину 6, длина пути будет 10+8=18, но в вершину 6 есть более короткий путь равный 16, поэтому забываем про путь равный 18. Из вершины 5 можно попасть в вершину 9, длина пути будет 10+41=51. Из вершины 5 можно попасть в вершину 10, длина пути будет 10+10=20.Запишем это в следующую строку таблицы:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

В новой строке минимальное значение равно 16. Выделим его жирным шрифтом.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

Кратчайший путь длиной 16 ведет к вершине 6 из вершины 1. Далее смотрим, куда можно попасть из вершины 6. Из вершины 6 можно попасть в вершину 7, длина пути будет 16+11=27. Из вершины 6 можно попасть в вершину 9, длина пути будет 16+44=60, но в вершину 9 есть более короткий путь равный 51, поэтому забываем про путь равный 60. Запишем это в следующую строку таблицы:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

В новой строке минимальное значение равно 20. Выделим его жирным шрифтом.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

Кратчайший путь длиной 20 ведет к вершине 10 из вершины 1. Далее смотрим, куда можно попасть из вершины 10. Из вершины 10 можно попасть в вершину 9, длина пути будет 20+5=25. Из вершины 10 можно попасть в вершину 5, длина пути будет 20+50=70, но в вершину 5 есть более короткий путь равный 10, поэтому забываем про путь равный 70. Запишем это в следующую строку таблицы:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

В новой строке минимальное значение равно 21. Выделим его жирным шрифтом.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

Кратчайший путь длиной 21 ведет к вершине 3 из вершины 1. Далее смотрим, куда можно попасть из вершины 3. Из вершины 3 можно попасть в вершину 4, длина пути будет 21+15=36. Из вершины 3 можно попасть в вершину 7, длина пути будет 21+18=39, но в вершину 7 есть более короткий путь равный 27, поэтому забываем про путь равный 39. Запишем это в следующую строку таблицы:

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

В новой строке минимальное значение равно 25. Выделим его жирным шрифтом. Длина пути в 25 – есть кратчайшее расстояние от вершины 1 до вершины 9.

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

При необходимости можно было бы продолжить работу с таблицей. Но задача решена, искомый путь найден.

Ответ: 25.

-75%

Курсы повышения квалификации

Профессиональная компетентность педагогов в условиях внедрения ФГОС

Продолжительность 72 часа

4000 руб.

1000 руб.

Информатика 3 класс

Информатика 10 класс (Россия)

Электронная тетрадь по информатике 10...

Информатика 7 класс (Россия)

Видеоуроки по информатике 6 класс (к...

Информатика 6 класс ФГОС

Информатика 9 класс ФГОС

Электронная тетрадь по информатике 5...

Скачать

Алгоритм Дейкстры

Просмотр содержимого документа
«Алгоритм Дейкстры»

Рекомендуем курсы ПК и ППК для учителей

Похожие файлы

Вебинар для учителей

Полезное для учителя

	1	2	3	4	5	6	7	8	9	10
1	0	7	∞	∞	10	∞	∞	∞	∞	∞
2		0	14			9
3			0	15			18
4				0				21
5					0	8			41	10
6						0	11		44
7				5			0	15		16
8								0		17
9									0
10					50				5	0

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

	1	2	3	4	5	6	7	8	9	10
1	0	7	∞	∞	10	∞	∞	∞	∞	∞
2		0	14			9
3			0	15			18
4				0				21
5					0	8			41	10
6						0	11		44
7				5			0	15		16
8								0		17
9									0
10					50				5	0

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

Алгоритм Дейкстры

Просмотр содержимого документа «Алгоритм Дейкстры»

Рекомендуем курсы ПК и ППК для учителей

Похожие файлы

Вебинар для учителей

Полезное для учителя

Просмотр содержимого документа
«Алгоритм Дейкстры»

	1	2	3	4	5	6	7	8	9	10
1	0	7	∞	∞	10	∞	∞	∞	∞	∞
2		0	14			9
3			0	15			18
4				0				21
5					0	8			41	10
6						0	11		44
7				5			0	15		16
8								0		17
9									0
10					50				5	0

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25

1	2	3	4	5	6	7	8	9	10
	7	∞	∞	10	∞	∞	∞	∞	∞
		21	∞	10	16	∞	∞	∞	∞
		21	∞		16	∞	∞	51	20
		21	∞			27	∞	51	20
		21	∞			27	∞	25
			36			27	∞	25