Кратчайший путь в графе — задачи с решениями (9 класс)
Типовые задачи по теме «Кратчайший путь в графе» с пошаговыми решениями. Если нужен не разбор, а тренировка с проверкой — начните с тренажёра.
Задача 1
Граф: A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2. Кратчайший путь от C до E? (число)
Решение:
1
Строим граф.
A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2
2
Применяем алгоритм Дейкстры.
Кратчайший путь C → E
3
Ответ.
Расстояние = 4
Ответ: 4
Задача 2
Граф: A-B:2, B-C:3, C-D:1, D-E:5. Кратчайший путь от C до E? (число)
Решение:
1
Строим граф.
A-B:2, B-C:3, C-D:1, D-E:5
2
Применяем алгоритм Дейкстры.
Кратчайший путь C → E
3
Ответ.
Расстояние = 6
Ответ: 6
Задача 3
Граф: 1-3:1, 1-end:10, 2-3:3, 2-end:8, 3-end:2. Кратчайший путь от 2 до 3? (число)
Решение:
1
Строим граф.
1-3:1, 1-end:10, 2-3:3, 2-end:8, 3-end:2
2
Применяем алгоритм Дейкстры.
Кратчайший путь 2 → 3
3
Ответ.
Расстояние = 3
Ответ: 3
Задача 4
Граф: A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2. Кратчайший путь от A до F? (число)
Решение:
1
Строим граф.
A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2
2
Применяем алгоритм Дейкстры.
Кратчайший путь A → F
3
Ответ.
Расстояние = 9
Ответ: 9
Задача 5
Граф: 1-2:10, 1-3:3, 2-3:1, 2-4:2, 3-4:8, 3-5:2, 4-5:7. Кратчайший путь от 3 до 4? (число)
Решение:
1
Строим граф.
1-2:10, 1-3:3, 2-3:1, 2-4:2, 3-4:8, 3-5:2, 4-5:7
2
Применяем алгоритм Дейкстры.
Кратчайший путь 3 → 4
3
Ответ.
Расстояние = 6
Ответ: 6
Задача 6
Граф: A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2. Кратчайший путь от B до C? (число)
Решение:
1
Строим граф.
A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2
2
Применяем алгоритм Дейкстры.
Кратчайший путь B → C
3
Ответ.
Расстояние = 2
Ответ: 2
Задача 7
Граф: A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2. Кратчайший путь от C до F? (число)
Решение:
1
Строим граф.
A-B:1, A-C:4, B-C:2, B-D:5, C-D:1, C-E:8, D-E:3, D-F:7, E-F:2
2
Применяем алгоритм Дейкстры.
Кратчайший путь C → F
3
Ответ.
Расстояние = 6
Ответ: 6
Задача 8
Граф: A-B:2, A-C:5, B-D:3, C-D:1, D-E:4. Кратчайший путь от E до B? (число)
Решение:
1
Строим граф.
A-B:2, A-C:5, B-D:3, C-D:1, D-E:4
2
Применяем алгоритм Дейкстры.
Кратчайший путь E → B
3
Ответ.
Расстояние = 7
Ответ: 7
Задача 9
Граф: A-B:2, B-C:3, C-D:1, D-E:5. Кратчайший путь от C до D? (число)
Решение:
1
Строим граф.
A-B:2, B-C:3, C-D:1, D-E:5
2
Применяем алгоритм Дейкстры.
Кратчайший путь C → D
3
Ответ.
Расстояние = 1
Ответ: 1
Задача 10
Граф: 1-2:10, 1-3:3, 2-3:1, 2-4:2, 3-4:8, 3-5:2, 4-5:7. Кратчайший путь от 1 до 5? (число)
Решение:
1
Строим граф.
1-2:10, 1-3:3, 2-3:1, 2-4:2, 3-4:8, 3-5:2, 4-5:7
2
Применяем алгоритм Дейкстры.
Кратчайший путь 1 → 5
3
Ответ.
Расстояние = 5
Ответ: 5
Хотите попробовать свои силы?
На платформе тысячи задач с автопроверкой и умными подсказками.
Перейти к задачам