Главная — Семестр 2
Обновлено: 08 April 2019

Сделать:

  1. Написать функцию поиска кратчайшео пути между двумя вершинами в заданном графе
  2. Найти все пути и выч слить расстояния от всех до всех вершин
  3. Определить столицу, как вершину:
    • сумма расстояний минимальная
    • сумма квадратов растойний минимальна
    • как центр графа

Данные:

Теория

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

основное действие: Если текущее расстояние от вершины i до вершины j больше, чем расстояние от вершины i до k + от k до j, то запоминаем новые данные (расстояние и вершину из которой пришли).