Теория:
Граф — это набор вершин и соединяющих их рёбер (вспомнить теорию).
Взвешенный граф — это граф, у которого каждое ребро связано с некоторым числом (это его вес).
Вес может обозначать расстояние между пунктами или стоимость проезда между ними.
Взвешенный граф можно описать в виде таблицы, где на пересечении столбца и строки стоит вес ребра данных вершин, если таковое существует.
Рис. \(1\). Граф
Рис. \(2\). Таблица, описывающая граф
Рис. \(3\). Граф, построенный по таблице
Граф по таблице может быть нарисован по-разному; например, граф на рисунке \(1\) (сверху от таблицы) и граф на рисунке \(3\) (снизу от таблицы) — одинаковые.
Обычно таблица симметрична относительно главной диагонали, это означает, что проезд из А в В и обратно одинаковый. (Что бывает не всегда, надо проверять!)
Источники:
Рис. 1. Граф. © ЯКласс.
Рис. 2. Таблица, описывающая граф. © ЯКласс.
Рис. 3. Граф, построенный по таблице. © ЯКласс.