Решение заданий по информатике. Формальные описания реальных объектов и процессов
Свириденко Н.А.
учитель информатики
МБОУ «Лицей №34»
г.Новокузнецк
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Вот как выглядит граф на примере обычной карты Гугл
Граф это графическая информационная модель, которая состоит из вершин, связанных линиями — рёбрами. Вершины графа могут изображаться кругами, овалами, точками, прямоугольниками, да чем угодно, хоть сердечками, просто буквами или загагулинами. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер (например расстояние между двумя точками - это вес ребра графа).
И если мне необходимо проложить маршрут по карте, я возьму линейку, бумажную карту и проложу кратчайший маршрут (мое зрение сделает 80% работы).
Для решения задания нам необходимо преобразовать табличную информацию в граф.
шаг 1 анализируем первую строчку: город А связан с городом В (расстояние = 2), город А связан с городом С (расстояние = 5), город А связан с городом D (расстояние = 1) . Строим граф:
шаг 2 анализируем вторую строчку: город B связан с городом A (расстояние = 2 на графе информация уже есть), город В связан с городом С (расстояние = 1) . Достроим граф:
шаг 3 анализируем третью строчку: город С связан с городом А (расстояние = 5 на графе информация уже есть), город С связан с городом В (расстояние = 1 на графе информация уже есть), город С связан с городом D (расстояние = 3), город С связан с городом Е (расстояние = 2) . Достроим граф:
шаг 4 анализируем четвертую строчку: город D связан с городом A (расстояние = 1 на графе информация уже есть), город D связан с городом С (расстояние = 3 на графе информация уже есть). шаг 5 анализируем пятую строчку: город Е связан с городом С (расстояние = 2 на графе информация уже есть)
шаг 6 анализируем граф и находим кратчайший путь из А в Е: А-В-С-Е складываем расстояния 2+1+2=5.
Основано на учебнике Босовой Людмилы Леонидовны
