Дана таблица длин дорог между пунктами. Нужно найти длину кратчайшего пути между двумя пунктами, иногда — с обязательным заездом в третий.
Как читать таблицу
На пересечении строки и столбца — длина дороги между пунктами.
Пустая клетка — прямой дороги нет.
Таблица симметрична: из A в B столько же, сколько из B в A.
Как решать
Нарисовать схему: пункты — точки, дороги — линии с длинами.
Перебрать пути от начала к концу, не заходя в пункт дважды.
Выбрать наименьшую сумму. Прямая дорога не обязательно самая короткая.
Типичные ошибки
Взять прямую дорогу и не проверить объезды.
Пропустить дорогу при переносе таблицы на схему.
В задаче «через пункт» забыть заехать в этот пункт.
Разобранные варианты
Сначала реши сам, потом открой разбор. В разборе — самые короткие пути и программа на Python.
Вариант 1
5 пунктов
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
6
4
4
B
5
2
C
6
5
8
5
D
4
8
8
E
4
2
5
8
Определите длину кратчайшего пути между пунктами B и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги B–D нет.
Шаг 2. Перебираем пути из B в D, не заходя в пункт дважды. Всего таких путей 10; самые короткие:
Путь
Длины дорог
Итого
B–E–A–D
2 + 4 + 4
10
B–E–D
2 + 8
10
B–C–D
5 + 8
13
B–C–A–D
5 + 6 + 4
15
B–E–C–D
2 + 5 + 8
15
B–E–C–A–D
2 + 5 + 6 + 4
17
Шаг 3. Наименьшая длина — 10 км.
Ответ: 10
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'C': 6, 'D': 4, 'E': 4}, 'B': {'C': 5, 'E': 2}, 'C': {'A': 6, 'B': 5, 'D': 8, 'E': 5}, 'D': {'A': 4, 'C': 8, 'E': 8}, 'E': {'A': 4, 'B': 2, 'C': 5, 'D': 8}}
best = None
def go(v, visited, dist):
global best
if v == 'D':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('B', {'B'}, 0)
print(best)
Вариант 2
5 пунктов
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
4
7
B
2
7
C
2
7
9
D
4
7
E
7
7
9
Определите длину кратчайшего пути между пунктами B и A. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги B–A нет.
Шаг 2. Перебираем пути из B в A, не заходя в пункт дважды. Всего таких путей 4; самые короткие:
Путь
Длины дорог
Итого
B–C–D–A
2 + 7 + 4
13
B–E–A
7 + 7
14
B–C–E–A
2 + 9 + 7
18
B–E–C–D–A
7 + 9 + 7 + 4
27
Шаг 3. Наименьшая длина — 13 км.
Ответ: 13
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'D': 4, 'E': 7}, 'B': {'C': 2, 'E': 7}, 'C': {'B': 2, 'D': 7, 'E': 9}, 'D': {'A': 4, 'C': 7}, 'E': {'A': 7, 'B': 7, 'C': 9}}
best = None
def go(v, visited, dist):
global best
if v == 'A':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('B', {'B'}, 0)
print(best)
Вариант 3
5 пунктов
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
4
1
1
8
B
4
8
1
C
1
8
D
1
1
4
E
8
4
Определите длину кратчайшего пути между пунктами B и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямая дорога B–C длиной 8 км длиннее объезда.
Шаг 2. Перебираем пути из B в C, не заходя в пункт дважды. Всего таких путей 4; самые короткие:
Путь
Длины дорог
Итого
B–D–A–C
1 + 1 + 1
3
B–A–C
4 + 1
5
B–C
8
8
B–D–E–A–C
1 + 4 + 8 + 1
14
Шаг 3. Наименьшая длина — 3 км.
Ответ: 3
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'B': 4, 'C': 1, 'D': 1, 'E': 8}, 'B': {'A': 4, 'C': 8, 'D': 1}, 'C': {'A': 1, 'B': 8}, 'D': {'A': 1, 'B': 1, 'E': 4}, 'E': {'A': 8, 'D': 4}}
best = None
def go(v, visited, dist):
global best
if v == 'C':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('B', {'B'}, 0)
print(best)
Вариант 4
5 пунктов
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
3
6
9
B
8
9
8
C
3
8
5
D
6
9
E
9
8
5
Определите длину кратчайшего пути между пунктами D и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги D–E нет.
Шаг 2. Перебираем пути из D в E, не заходя в пункт дважды. Всего таких путей 6; самые короткие:
Путь
Длины дорог
Итого
D–A–C–E
6 + 3 + 5
14
D–A–E
6 + 9
15
D–B–E
9 + 8
17
D–B–C–E
9 + 8 + 5
22
D–A–C–B–E
6 + 3 + 8 + 8
25
D–B–C–A–E
9 + 8 + 3 + 9
29
Шаг 3. Наименьшая длина — 14 км.
Ответ: 14
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'C': 3, 'D': 6, 'E': 9}, 'B': {'C': 8, 'D': 9, 'E': 8}, 'C': {'A': 3, 'B': 8, 'E': 5}, 'D': {'A': 6, 'B': 9}, 'E': {'A': 9, 'B': 8, 'C': 5}}
best = None
def go(v, visited, dist):
global best
if v == 'E':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('D', {'D'}, 0)
print(best)
Вариант 5
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
8
2
6
2
B
1
2
4
9
C
8
1
1
D
2
2
1
1
E
6
4
9
F
2
9
1
9
Определите длину кратчайшего пути между пунктами E и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямая дорога E–F длиной 9 км длиннее объезда.
Шаг 2. Перебираем пути из E в F, не заходя в пункт дважды. Всего таких путей 17; самые короткие:
Путь
Длины дорог
Итого
E–B–C–D–F
4 + 1 + 1 + 1
7
E–B–D–F
4 + 2 + 1
7
E–A–F
6 + 2
8
E–A–D–F
6 + 2 + 1
9
E–F
9
9
E–B–C–D–A–F
4 + 1 + 1 + 2 + 2
10
Шаг 3. Наименьшая длина — 7 км.
Ответ: 7
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'C': 8, 'D': 2, 'E': 6, 'F': 2}, 'B': {'C': 1, 'D': 2, 'E': 4, 'F': 9}, 'C': {'A': 8, 'B': 1, 'D': 1}, 'D': {'A': 2, 'B': 2, 'C': 1, 'F': 1}, 'E': {'A': 6, 'B': 4, 'F': 9}, 'F': {'A': 2, 'B': 9, 'D': 1, 'E': 9}}
best = None
def go(v, visited, dist):
global best
if v == 'F':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('E', {'E'}, 0)
print(best)
Вариант 6
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
6
7
3
6
B
2
C
6
2
8
2
D
7
8
3
E
3
8
8
5
F
6
2
3
5
Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги B–E нет.
Шаг 2. Перебираем пути из B в E, не заходя в пункт дважды. Всего таких путей 11; самые короткие:
Путь
Длины дорог
Итого
B–C–F–E
2 + 2 + 5
9
B–C–E
2 + 8
10
B–C–A–E
2 + 6 + 3
11
B–C–F–A–E
2 + 2 + 6 + 3
13
B–C–F–D–E
2 + 2 + 3 + 8
15
B–C–F–D–A–E
2 + 2 + 3 + 7 + 3
17
Шаг 3. Наименьшая длина — 9 км.
Ответ: 9
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'C': 6, 'D': 7, 'E': 3, 'F': 6}, 'B': {'C': 2}, 'C': {'A': 6, 'B': 2, 'E': 8, 'F': 2}, 'D': {'A': 7, 'E': 8, 'F': 3}, 'E': {'A': 3, 'C': 8, 'D': 8, 'F': 5}, 'F': {'A': 6, 'C': 2, 'D': 3, 'E': 5}}
best = None
def go(v, visited, dist):
global best
if v == 'E':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('B', {'B'}, 0)
print(best)
Вариант 7
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
1
5
1
B
1
9
9
7
6
C
5
9
D
1
9
E
7
F
6
Определите длину кратчайшего пути между пунктами F и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги F–D нет.
Шаг 2. Перебираем пути из F в D, не заходя в пункт дважды. Всего таких путей 3; самые короткие:
Путь
Длины дорог
Итого
F–B–A–D
6 + 1 + 1
8
F–B–D
6 + 9
15
F–B–C–A–D
6 + 9 + 5 + 1
21
Шаг 3. Наименьшая длина — 8 км.
Ответ: 8
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'B': 1, 'C': 5, 'D': 1}, 'B': {'A': 1, 'C': 9, 'D': 9, 'E': 7, 'F': 6}, 'C': {'A': 5, 'B': 9}, 'D': {'A': 1, 'B': 9}, 'E': {'B': 7}, 'F': {'B': 6}}
best = None
def go(v, visited, dist):
global best
if v == 'D':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('F', {'F'}, 0)
print(best)
Вариант 8
5 пунктов · через D
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
7
1
B
8
3
C
7
8
3
2
D
3
3
2
E
1
2
2
Определите длину кратчайшего пути между пунктами A и B, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги A–B нет.
Шаг 2. Перебираем пути из A в B через D, не заходя в пункт дважды. Всего таких путей 5; самые короткие:
Путь
Длины дорог
Итого
A–E–D–B
1 + 2 + 3
6
A–E–C–D–B
1 + 2 + 3 + 3
9
A–C–D–B
7 + 3 + 3
13
A–C–E–D–B
7 + 2 + 2 + 3
14
A–E–D–C–B
1 + 2 + 3 + 8
14
Шаг 3. Наименьшая длина — 6 км.
Ответ: 6
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'C': 7, 'E': 1}, 'B': {'C': 8, 'D': 3}, 'C': {'A': 7, 'B': 8, 'D': 3, 'E': 2}, 'D': {'B': 3, 'C': 3, 'E': 2}, 'E': {'A': 1, 'C': 2, 'D': 2}}
best = None
def go(v, visited, dist):
global best
if v == 'B':
if 'D' in visited and (best is None or dist < best):
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('A', {'A'}, 0)
print(best)
Вариант 9
6 пунктов · через F
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
4
5
3
B
4
6
7
C
5
6
2
2
D
2
9
9
E
3
9
F
7
2
9
Определите длину кратчайшего пути между пунктами E и B, проходящего через пункт F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямой дороги E–B нет.
Шаг 2. Перебираем пути из E в B через F, не заходя в пункт дважды. Всего таких путей 6; самые короткие:
Путь
Длины дорог
Итого
E–A–C–F–B
3 + 5 + 2 + 7
17
E–D–C–F–B
9 + 2 + 2 + 7
20
E–D–F–B
9 + 9 + 7
25
E–A–C–D–F–B
3 + 5 + 2 + 9 + 7
26
E–D–F–C–B
9 + 9 + 2 + 6
26
E–D–F–C–A–B
9 + 9 + 2 + 5 + 4
29
Шаг 3. Наименьшая длина — 17 км.
Ответ: 17
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'B': 4, 'C': 5, 'E': 3}, 'B': {'A': 4, 'C': 6, 'F': 7}, 'C': {'A': 5, 'B': 6, 'D': 2, 'F': 2}, 'D': {'C': 2, 'E': 9, 'F': 9}, 'E': {'A': 3, 'D': 9}, 'F': {'B': 7, 'C': 2, 'D': 9}}
best = None
def go(v, visited, dist):
global best
if v == 'B':
if 'F' in visited and (best is None or dist < best):
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('E', {'E'}, 0)
print(best)
Вариант 10
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
1
6
1
B
1
3
2
C
9
6
D
6
3
9
7
E
1
7
7
F
2
6
7
Определите длину кратчайшего пути между пунктами D и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Разбор
Шаг 1. Смотрим, куда можно поехать. В строке пункта записаны длины дорог из него; пустая клетка — дороги нет. Прямая дорога D–E длиной 7 км длиннее объезда.
Шаг 2. Перебираем пути из D в E, не заходя в пункт дважды. Всего таких путей 7; самые короткие:
Путь
Длины дорог
Итого
D–B–A–E
3 + 1 + 1
5
D–A–E
6 + 1
7
D–E
7
7
D–B–F–E
3 + 2 + 7
12
D–A–B–F–E
6 + 1 + 2 + 7
16
D–C–F–B–A–E
9 + 6 + 2 + 1 + 1
19
Шаг 3. Наименьшая длина — 5 км.
Ответ: 5
Решение на Python. Рекурсивный перебор всех путей без повторов пунктов.
roads = {'A': {'B': 1, 'D': 6, 'E': 1}, 'B': {'A': 1, 'D': 3, 'F': 2}, 'C': {'D': 9, 'F': 6}, 'D': {'A': 6, 'B': 3, 'C': 9, 'E': 7}, 'E': {'A': 1, 'D': 7, 'F': 7}, 'F': {'B': 2, 'C': 6, 'E': 7}}
best = None
def go(v, visited, dist):
global best
if v == 'E':
if best is None or dist < best:
best = dist
return
for u, w in roads[v].items():
if u not in visited:
go(u, visited | {u}, dist + w)
go('D', {'D'}, 0)
print(best)
Для самостоятельного решения
Варианты 11–15 без разборов. Ответ можно проверить кнопкой.
Вариант 11
5 пунктов
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
9
B
1
7
2
C
9
1
9
D
7
9
9
E
2
9
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Вариант 12
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
4
9
3
3
B
4
6
1
9
C
9
6
5
3
D
3
1
5
7
2
E
3
9
3
7
F
2
Определите длину кратчайшего пути между пунктами F и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Вариант 13
6 пунктов · через D
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
2
4
1
1
B
2
7
1
9
C
4
7
5
5
7
D
1
5
E
1
9
5
8
F
1
7
8
Определите длину кратчайшего пути между пунктами F и B, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Вариант 14
5 пунктов · через D
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
A
4
3
2
8
B
4
3
5
C
3
9
D
2
3
2
E
8
5
9
2
Определите длину кратчайшего пути между пунктами C и E, проходящего через пункт D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Вариант 15
6 пунктов
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A
B
C
D
E
F
A
4
1
8
B
4
1
2
8
4
C
1
3
4
D
1
2
3
1
E
8
4
1
F
8
4
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.