КАРТОЧКИ
ТЕСТЫ
Главная
Курсы
4. Работа с таблицами: все задания
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $3$ | $3$ | |||
| $B$ | $3$ | $5$ | $6$ | ||
| $C$ | $3$ | $4$ | |||
| $D$ | $5$ | $4$ | $1$ | ||
| $E$ | $6$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$.
- Путь $A\to B\to E$ имеет длину: $3+6=9$.
- Путь $A\to B\to D\to E$ имеет длину: $3+5+1=9$.
- Путь $A\to C\to D\to E$ имеет длину: $3+4+1=8$.
- Путь $A\to C\to D\to B\to E$ имеет длину: $3+4+5+6=18$.
Наименьшую длину имеет путь $A\to C\to D\to E$.
Длина кратчайшего пути: $8$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $1$ | $4$ | $5$ | $6$ | |
| $B$ | $1$ | $3$ | $2$ | ||
| $C$ | $4$ | $2$ | |||
| $D$ | $5$ | $3$ | $1$ | ||
| $E$ | $6$ | $2$ | $2$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $D$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $D$.
- Прямой путь $A\to D$ имеет длину: $5$.
- Путь $A\to B\to D$ имеет длину: $1+3=4$.
- Путь $A\to E\to D$ имеет длину: $6+1=7$.
- Путь $A\to B\to E\to D$ имеет длину: $1+2+1=4$.
- Путь $A\to C\to E\to D$ имеет длину: $4+2+1=7$.
- Путь $A\to E\to B\to D$ имеет длину: $6+2+3=11$.
- Путь $A\to C\to E\to B\to D$ имеет длину: $4+2+2+3=11$.
Наименьшую длину имеют пути $A\to B\to D$ и $A\to B\to E\to D$.
Длина кратчайшего пути: $4$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $7$ | $4$ | |||
| $B$ | $7$ | $2$ | $5$ | ||
| $C$ | $4$ | $2$ | $4$ | ||
| $D$ | $4$ | $5$ | |||
| $E$ | $5$ | $5$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$.
- Путь $A\to B\to E$ имеет длину: $7+5=12$.
- Путь $A\to C\to B\to E$ имеет длину: $4+2+5=11$.
- Путь $A\to C\to D\to E$ имеет длину: $4+4+5=13$.
- Путь $A\to B\to C\to D\to E$ имеет длину: $7+2+4+5=18$.
Наименьшую длину имеет путь $A\to C\to B\to E$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $2$ | $5$ | $1$ | ||
| $B$ | $2$ | $1$ | |||
| $C$ | $5$ | $1$ | $3$ | $2$ | |
| $D$ | $1$ | $3$ | |||
| $E$ | $2$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$.
- Путь $A\to C\to E$ имеет длину: $5+2=7$.
- Путь $A\to B\to C\to E$ имеет длину: $2+1+2=5$.
- Путь $A\to D\to C\to E$ имеет длину: $1+3+2=6$.
Наименьшую длину имеет путь $A\to B\to C\to E$.
Длина кратчайшего пути: $5$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $7$ | $4$ | |||
| $B$ | $7$ | $2$ | $6$ | $2$ | |
| $C$ | $2$ | $3$ | |||
| $D$ | $6$ | $3$ | $8$ | ||
| $E$ | $4$ | $2$ | $8$ |
Определите длину кратчайшего пути между пунктами $A$ и $D$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $D$.
- Путь $A\to B\to D$ имеет длину: $7+6=13$.
- Путь $A\to E\to D$ имеет длину: $4+8=12$.
- Путь $A\to B\to C\to D$ имеет длину: $7+2+3=12$.
- Путь $A\to E\to B\to D$ имеет длину: $4+2+6=12$.
- Путь $A\to B\to E\to D$ имеет длину: $7+2+8=17$.
- Путь $A\to E\to B\to C\to D$ имеет длину: $4+2+2+3=11$.
Наименьшую длину имеет путь $A\to E\to B\to C\to D$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $4$ | $2$ | $8$ | ||
| $B$ | $4$ | $7$ | |||
| $C$ | $2$ | $7$ | $2$ | $6$ | |
| $D$ | $2$ | $3$ | |||
| $E$ | $8$ | $6$ | $3$ |
Определите длину кратчайшего пути между пунктами $B$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $B$ в пункт $E$.
- Путь $B\to A\to E$ имеет длину: $4+8=12$.
- Путь $B\to A\to C\to E$ имеет длину: $4+2+6=12$.
- Путь $B\to A\to C\to D\to E$ имеет длину: $4+2+2+3=11$.
- Путь $B\to C\to E$ имеет длину: $7+6=13$.
- Путь $B\to C\to D\to E$ имеет длину: $7+2+3=12$.
- Путь $B\to C\to A\to E$ имеет длину: $7+2+8=17$.
Наименьшую длину имеет путь $B\to A\to C\to D\to E$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $4$ | ||||
| $B$ | $4$ | $4$ | $1$ | ||
| $C$ | $4$ | $1$ | $2$ | ||
| $D$ | $1$ | $3$ | |||
| $E$ | $1$ | $2$ | $3$ |
Определите длину кратчайшего пути между пунктами $A$ и $D$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $D$.
- Путь $A\to B\to C\to D$ имеет длину: $4+4+1=9$.
- Путь $A\to B\to E\to D$ имеет длину: $4+1+3=8$.
- Путь $A\to B\to E\to C\to D$ имеет длину: $4+1+2+1=8$.
- Путь $A\to B\to C\to E\to D$ имеет длину: $4+4+2+3=13$.
Наименьшую длину имеют пути $A\to B\to E\to D$ и $A\to B\to E\to C\to D$.
Длина кратчайшего пути: $8$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $7$ | $4$ | |||
| $B$ | $7$ | $2$ | $4$ | ||
| $C$ | $4$ | $2$ | $4$ | ||
| $D$ | $4$ | $4$ | |||
| $E$ | $4$ | $4$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$, проходящего через пункт $C$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$, проходящие через пункт $C$.
- Путь $A\to C\to B\to E$ имеет длину: $4+2+4=10$.
- Путь $A\to C\to D\to E$ имеет длину: $4+4+4=12$.
- Путь $A\to B\to C\to D\to E$ имеет длину: $7+2+4+4=17$.
Наименьшую длину имеет путь $A\to C\to B\to E$.
Длина кратчайшего пути: $10$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$, $F$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | |
|---|---|---|---|---|---|---|
| $A$ | $2$ | $5$ | $15$ | |||
| $B$ | $2$ | $2$ | ||||
| $C$ | $5$ | $2$ | $1$ | $3$ | ||
| $D$ | $1$ | $6$ | ||||
| $E$ | $3$ | $4$ | ||||
| $F$ | $15$ | $6$ | $4$ |
Определите длину кратчайшего пути между пунктами $A$ и $F$, проходящего через пункт $C$. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $F$, проходящие через пункт $C$.
- Путь $A\to C\to D\to F$ имеет длину: $5+1+6=12$.
- Путь $A\to C\to E\to F$ имеет длину: $5+3+4=12$.
- Путь $A\to B\to C\to D\to F$ имеет длину: $2+2+1+6=11$.
- Путь $A\to B\to C\to E\to F$ имеет длину: $2+2+3+4=11$.
Наименьшую длину имеют пути $A\to B\to C\to D\to F$ и $A\to B\to C\to E\to F$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $5$ | $8$ | $8$ | $12$ | |
| $B$ | $5$ | $4$ | |||
| $C$ | $8$ | $7$ | |||
| $D$ | $8$ | $4$ | $5$ | ||
| $E$ | $12$ | $7$ | $5$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$ (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$.
- Прямой путь $A\to E$ имеет длину: $12$.
- Путь $A\to D\to E$ имеет длину: $8+5=13$.
- Путь $A\to C\to E$ имеет длину: $8+7=15$.
- Путь $A\to B\to D\to E$ имеет длину: $5+4+5=14$.
Наименьшую длину имеет прямой путь $A\to E$.
Длина кратчайшего пути: $12$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | |
|---|---|---|---|---|
| $A$ | $2$ | $7$ | $4$ | |
| $B$ | $2$ | $5$ | $1$ | |
| $C$ | $7$ | $5$ | $2$ | |
| $D$ | $4$ | $1$ | $2$ |
Определите длину кратчайшего пути между пунктами $A$ и $C$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $C$.
- Прямой путь $A\to C$ имеет длину: $7$.
- Путь $A\to B\to C$ имеет длину: $2+5=7$.
- Путь $A\to D\to C$ имеет длину: $4+2=6$.
- Путь $A\to B\to D\to C$ имеет длину: $2+1+2=5$.
- Путь $A\to D\to B\to C$ имеет длину: $4+1+5=10$.
Наименьшую длину имеет путь $A\to B\to D\to C$.
Длина кратчайшего пути: $5$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $5$ | $6$ | $10$ | $5$ | |
| $B$ | $5$ | $4$ | |||
| $C$ | $6$ | $2$ | $7$ | ||
| $D$ | $10$ | $4$ | $2$ | $5$ | |
| $E$ | $5$ | $7$ | $5$ |
Определите длину кратчайшего пути между пунктами $A$ и $D$, проходящего через пункт $E$ (при условии, что передвигаться можно только по указанным в таблице дорогам). Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $D$, проходящие через пункт $E$.
- Путь $A\to E\to D$ имеет длину: $5+5=10$.
- Путь $A\to E\to C\to D$ имеет длину: $5+7+2=14$.
- Путь $A\to C\to E\to D$ имеет длину: $6+7+5=18$.
Наименьшую длину имеет путь $A\to E\to D$.
Длина кратчайшего пути: $10$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$, $F$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | |
|---|---|---|---|---|---|---|
| $A$ | $3$ | $4$ | $18$ | |||
| $B$ | $3$ | $3$ | ||||
| $C$ | $4$ | $3$ | $4$ | |||
| $D$ | $4$ | $2$ | $6$ | |||
| $E$ | $2$ | $1$ | ||||
| $F$ | $18$ | $6$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $F$. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $F$.
- Прямой путь $A\to F$ имеет длину: $18$.
- Путь $A\to C\to D\to F$ имеет длину: $4+4+6=14$.
- Путь $A\to C\to D\to E\to F$ имеет длину: $4+4+2+1=11$.
- Путь $A\to B\to C\to D\to F$ имеет длину: $3+3+4+6=16$.
- Путь $A\to B\to C\to D\to E\to F$ имеет длину: $3+3+4+2+1=13$.
Наименьшую длину имеет путь $A\to C\to D\to E\to F$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$, $F$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | |
|---|---|---|---|---|---|---|
| $A$ | $3$ | $4$ | $15$ | |||
| $B$ | $3$ | $3$ | $4$ | |||
| $C$ | $4$ | $3$ | $1$ | $6$ | ||
| $D$ | $4$ | $1$ | $2$ | $6$ | ||
| $E$ | $2$ | $1$ | ||||
| $F$ | $15$ | $6$ | $6$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $F$, проходящего через пункт $C$. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $F$, проходящие через пункт $C$.
- Путь $A\to C\to F$ имеет длину: $4+6=10$.
- Путь $A\to C\to D\to F$ имеет длину: $4+1+6=11$.
- Путь $A\to C\to D\to E\to F$ имеет длину: $4+1+2+1=8$.
- Путь $A\to B\to C\to F$ имеет длину: $3+3+6=12$.
- Путь $A\to B\to C\to D\to E\to F$ имеет длину: $3+3+1+2+1=10$.
- Путь $A\to B\to D\to C\to F$ имеет длину: $3+4+1+6=14$.
Наименьшую длину имеет путь $A\to C\to D\to E\to F$.
Длина кратчайшего пути: $8$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $7$ | $2$ | $6$ | $2$ | |
| $B$ | $7$ | $4$ | |||
| $C$ | $2$ | $4$ | $8$ | ||
| $D$ | $6$ | $8$ | $3$ | ||
| $E$ | $2$ | $3$ |
Определите длину кратчайшего пути между пунктами $B$ и $D$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $B$ в пункт $D$.
- Путь $B\to C\to D$ имеет длину: $4+8=12$.
- Путь $B\to A\to D$ имеет длину: $7+6=13$.
- Путь $B\to A\to E\to D$ имеет длину: $7+2+3=12$.
- Путь $B\to C\to A\to D$ имеет длину: $4+2+6=12$.
- Путь $B\to C\to A\to E\to D$ имеет длину: $4+2+2+3=11$.
- Путь $B\to A\to C\to D$ имеет длину: $7+2+8=17$.
Наименьшую длину имеет путь $B\to C\to A\to E\to D$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $4$ | $4$ | |||
| $B$ | $4$ | $1$ | $5$ | ||
| $C$ | $4$ | $1$ | $3$ | ||
| $D$ | $5$ | $3$ | $1$ | ||
| $E$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$.
- Путь $A\to B\to D\to E$ имеет длину: $4+5+1=10$.
- Путь $A\to C\to D\to E$ имеет длину: $4+3+1=8$.
- Путь $A\to B\to C\to D\to E$ имеет длину: $4+1+3+1=9$.
- Путь $A\to C\to B\to D\to E$ имеет длину: $4+1+5+1=11$.
Наименьшую длину имеет путь $A\to C\to D\to E$.
Длина кратчайшего пути: $8$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$, $F$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | |
|---|---|---|---|---|---|---|
| $A$ | $1$ | $4$ | $15$ | |||
| $B$ | $1$ | $2$ | ||||
| $C$ | $4$ | $2$ | $5$ | |||
| $D$ | $5$ | $3$ | $3$ | |||
| $E$ | $3$ | $3$ | ||||
| $F$ | $15$ | $3$ | $3$ |
Определите длину кратчайшего пути между пунктами $A$ и $F$. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $F$.
- Прямой путь $A\to F$ имеет длину: $15$.
- Путь $A\to C\to D\to F$ имеет длину: $4+5+3=12$.
- Путь $A\to C\to D\to E\to F$ имеет длину: $4+5+3+3=15$.
- Путь $A\to B\to C\to D\to F$ имеет длину: $1+2+5+3=11$.
- Путь $A\to B\to C\to D\to E\to F$ имеет длину: $1+2+5+3+3=14$.
Наименьшую длину имеет путь $A\to B\to C\to D\to F$.
Длина кратчайшего пути: $11$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $2$ | $3$ | |||
| $B$ | $2$ | $1$ | $3$ | $5$ | |
| $C$ | $3$ | $1$ | $4$ | $3$ | |
| $D$ | $3$ | $4$ | $1$ | ||
| $E$ | $5$ | $3$ | $1$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$, проходящего через пункт $C$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$, проходящие через пункт $C$.
- Путь $A\to C\to E$ имеет длину: $3+3=6$.
- Путь $A\to B\to C\to E$ имеет длину: $2+1+3=6$.
- Путь $A\to C\to D\to E$ имеет длину: $3+4+1=8$.
- Путь $A\to C\to B\to D\to E$ имеет длину: $3+1+3+1=8$.
- Путь $A\to B\to C\to D\to E$ имеет длину: $2+1+4+1=8$.
- Путь $A\to B\to D\to C\to E$ имеет длину: $2+3+4+3=12$.
Наименьшую длину имеют пути $A\to C\to E$ и $A\to B\to C\to E$.
Длина кратчайшего пути: $6$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $1$ | $2$ | $4$ | ||
| $B$ | $4$ | ||||
| $C$ | $1$ | $4$ | $4$ | ||
| $D$ | $2$ | $4$ | $1$ | ||
| $E$ | $4$ | $1$ |
Определите длину кратчайшего пути между пунктами $B$ и $E$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $B$ в пункт $E$.
- Путь $B\to C\to D\to E$ имеет длину: $4+4+1=9$.
- Путь $B\to C\to A\to E$ имеет длину: $4+1+4=9$.
- Путь $B\to C\to A\to D\to E$ имеет длину: $4+1+2+1=8$.
- Путь $B\to C\to D\to A\to E$ имеет длину: $4+4+2+4=14$.
Наименьшую длину имеет путь $B\to C\to A\to D\to E$.
Длина кратчайшего пути: $8$.
20
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых (в километрах) приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $2$ | $3$ | |||
| $B$ | $2$ | $5$ | $2$ | $4$ | |
| $C$ | $5$ | $1$ | |||
| $D$ | $2$ | $1$ | |||
| $E$ | $3$ | $4$ |
Определите длину кратчайшего пути между пунктами $A$ и $D$. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $D$.
- Путь $A\to B\to D$ имеет длину: $2+2=4$.
- Путь $A\to B\to C\to D$ имеет длину: $2+5+1=8$.
- Путь $A\to E\to B\to D$ имеет длину: $3+4+2=9$.
- Путь $A\to E\to B\to C\to D$ имеет длину: $3+4+5+1=13$.
Наименьшую длину имеет путь $A\to B\to D$.
Длина кратчайшего пути: $4$.
20