Оптимизация маршрута с помощью матрицы смежности
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Для удобства представим таблицу в виде графа:
Т.к. в пункт F можем попасть только из E, сейчас задача сводится к нахождению кратчайшего расстояния между А и Е.
Сейчас нужно аккуратно разобрать все случаи. Итак, если мы идем из А в В, до Е мы можем добраться следующими способами: A-B-E = 4 + 1 = 5, A-B-C-E = 4 + 7 + 4 = 15 – причем из графа видно, что в вершину D заходить не стоит: мы сделаем крюк.
Если мы идем из А в С, то до Е мы доходим так: А-С-Е = 2 + 4 = 6. Видим, что из А до Е наименьшее расстояние по маршруту A-B-E = 5. Тогда A-F = 5 + 2 = 7.
Между населёнными пунктами А, В, С, D, Е, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).
Для удобства представим таблицу в виде графа:
Прямой путь A-G = 34. Из А также можем попасть в B, D, C.
Из B в D можно попасть напрямую – длина 6, через С – длина 4 + 2 = 6, то есть из A через B в D – 4 + 6 = 10. Из A в D – напрямую за 15 или через C: 10 + 2 = 12. Тогда из A в D можно попасть по пути длиной 10.
Из D в G – по пути длиной 15 напрямую или через E и F. D-E-G = 3 + 9 = 12, D-E-F-G = 3 + 8 + 4 = 15, D-F-G = 11 + 4 = 15. То есть кратчайший путь из D в G – длиной 12. Тогда кратчайший путь из A в G = 10 + 12 = 22.
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами А и G (при условии, что передвигаться можно только по построенным дорогам).
Для удобства представим таблицу в виде графа:
Прямой путь из A в G – 25, из A в C самый короткий путь – через B (прямой = 9, через B – 4 + 3 = 7), C-F-G = 13 + 1 = 14, прямой путь из C в G = 20 > 14, C-D-E-G = 2 + 4 + 4 = 10 < 14, то есть из C кратчайший путь в G = 10, а кратчайший путь в C = 7, то есть весь путь из A в G = 7 + 10 = 17 < 25 (прямой путь из A в G). Тогда наш ответ – 17.
Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.
Для удобства представим таблицу в виде графа:
Прямой путь из A в F = 11. Путь из A в В, как видим, никуда не ведет, поэтому его не рассматриваем. Рассмотрим все остальные пути.
Если пойдем в С, пути будут такие:
1) A-C-F = 8;
2) A-C-D-F = 9;
3) A-C-D-E-F = 19.
Если пойдем в D:
1) A-D-F = 9;
2) A-D-C-F = 12;
3) A-D-E-F = 19.
Если пойдем в E:
1) A-E-F = 10;
2) A-E-D-F = 6;
3) A-E-D-C-F = 9.
Видим, что кратчайший путь = 6.
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет
Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам. В ответе укажите только число.
Для удобства представим таблицу в виде графа:
Из вершины A попасть в вершину D можно путем длины 5 (через В): прямой (длина = 6) и через С (длина = 2 + 5 + 1 = 8) больше, поэтому их мы не рассматриваем.
Из вершины D можно попасть в G через F – тогда длина пути = 7 + 7 = 14 – или через E – тогда длина = 9 + 5 = 14. То есть из D мы попадаем в G путем длины 14, тогда минимальный путь через D в G = 5 + 14 = 19.
Из C в G можно попасть за 8 (варианты, когда идем через D, уже рассмотрены выше – мы решили, что через С идти в D дольше, чем через B, поэтому этот вариант мы не рассматриваем). Попасть в С можно за 6: мы можем сделать это маршрутами A-D-C (длина = 6 + 1 = 7), A-B-D-C (длина = 2 + 3 + 1 = 6), A-B-C (длина = 2 + 5 = 7).
Значит, в С из А мы попадаем путем длины 6, а из С в G – 8. То есть из A в G через С – за 6 + 8 = 14 < 19 (путь через D). Значит, 14 – наш ответ.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.
Для удобства представим таблицу в виде графа:
Прямой путь из A в F = 16. Как видим из графа, через B и C мы можем пройти только в D, тогда определим наименьший путь из A в D: через B – 3 + 5 = 8, C – 4 + 2 = 6, прямой – 4. Итак, в D из A можно добраться путем длины 4.
Из D можно сразу добраться в F путем длины 10,а через E – путем длины 6 + 3 = 9. То есть через D добраться до F можно путем длины 4 + 9 = 13 < 16 (прямой путь из A в F). Значит, 13 – наш ответ.
