Графы: разбор задач и продолжение

Домашнее задание

  1. {i} Прочитать про алгоритмы Флойда и Дейкстры на сайте MCCME

  2. Решить задачи проверки свойств графа (4 и 5) с прошлого раза

  3. Таблица N×N содержит стоимости прямого проезда из города i в город j (i<N, j<N, i≠j). Стоимость проезда не превышает S, если из города i в город j проезда нет, в таблице стоит S*N.

    1. Определить минимальную стоимость проезда из города A в город B с учётом возможных пересадок
    2. составить таблицу минимальной стоимости проезда из любого города в любой
    3. …вывести также любой маршрут из A в B с минимальной стоимостью проезда

Условные обозначения


CategoryClass CategoryVmsh