Найди длину кратчайшего пути между вершинами I и А, состоящего из 4 рёбер.

Из вершины I в вершину А можно попасть несколькими путями, состоящими из 4 ребер. Необходимо найти кратчайший из них.

1) I → H → G → A: 6 + 2 + 1 = 9

2) I → D → C → B → A: 1 + 1 + 8 + 1 = 11

3) I → D → F → E → A: 1 + 2 + 3 + 1 = 7

4) I → D → C → A: невозможно, так как только 3 ребра

5) I → F → E → A: невозможно, так как только 3 ребра

6) I → F → C → A: невозможно, так как только 3 ребра

7) I → G → A: невозможно, так как только 2 ребра

8) I → F → E → B → A: 4 + 3 + 1 + 1= 9

9) I → H → G → E → A: 6 + 2 + 1 + 1= 10

10) I → F → B → A: невозможно, так как только 3 ребра

Минимальная длина пути I → D → F → E → A, равная 7.

Ответ: 7