×
  • 1. Количество информации в тексте
  • 2. Логические выражения
  • 3. Кратчайший путь в графе
  • 4. Файловая система
  • 5. Диаграммы в электронных таблицах
  • 6. Выполнение алгоритмов для исполнителей
  • 7. Кодирование и декодирование сообщений
  • 8. Оператор присваивания
  • 9. Программы с циклами
  • 10. Обработка массивов
  • 11. Количество путей в графе
  • 12. Базы данных. Проверка условия
  • 13. Двоичная система счисления
  • 14. Составление программ для исполнителя
  • 15. Скорость передачи данных
  • 16. Выполнение и анализ алгоритма для автомата
  • 17. Составление адреса URL из частей
  • 18. Поисковые запросы в Интернете
  • 19. Обработка данных в Excel
  • 21. Написание программы
  • Спасибо за внимание
  • Подготовка к ОГЭ по Информатике

    Задания на тему "Кратчайший путь в графе".


    1) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       3 1 2 6      
    B 3       1                  
    C 1 1                        
    D 2                   2      
    E 6             2       3
    F                         3      

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    2) Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F Z
    A       5 8 25             39
    B 5       1 20                  
    C 8 1       11             28
    D 25 20 11       4 6 10
    E                   4             8
    F                   6             2
    Z 39       28 10 8 2      

    Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

    3) Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F Z
    A       4 11                   25
    B 4       5                        
    C 11 5       3 8 12 22
    D             3       4            
    E             8 4             3
    F             12                   1
    Z 25       22       3 1      

    Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

    4) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       3 5             15
    B 3             4            
    C 5             1            
    D       4 1       2 6
    E                   2       1
    F 15             6 1      

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    5) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E
    A       2 4       5
    B 2       1            
    C 4 1       4 3
    D             4       3
    E 5       3 3      

    Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).

    6) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       8 3                  
    B 8             3            
    C 3                   4 3
    D       3             1 3
    E             4 1       2
    F             3 3 2      

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    7) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       5 3                  
    B 5             6 2      
    C 3                   5 4
    D       6             3 5
    E       2 5 3            
    F             4 5            

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    8) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E
    A             4 5 7
    B             1       3
    C 4 1       2 1
    D 5       2       1
    E 7 3 1 1      

    Определите длину кратчайшего пути между пунктами A и E (при условии, что передвигаться можно только по построенным дорогам).

    9) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E
    A       1                  
    B 1       2 2 7
    C       2             3
    D       2             4
    E       7 3 4      

    Определите длину кратчайшего пути между пунктами A и E (при условии, что передвигаться можно только по построенным дорогам).

    10) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       3                        
    B 3       2             7
    C       2             2      
    D                         1 1
    E             2 1       3
    F       7       1 3      

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    11) Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F
    A       1 5             15
    B 1       2                  
    C 5 2       1            
    D             1       2 6
    E                   2       1
    F 15             6 1      

    Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

    12) Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F Z
    A       4 10 15             34
    B 4       4 6                  
    C 10 4       2                  
    D 15 6 2       9 11 15
    E                   9             7
    F                   11             4
    Z 34             15 7 4      

    Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

    13) Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F Z
    A       4 9                   21
    B 4       3                        
    C 9 3       2       11 20
    D             2       4            
    E                   4             4
    F             11                   2
    Z 21       20       4 2      

    Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

    14) Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E F Z
    A       4 6                   33
    B 4       1                        
    C 6 1       5             27
    D             5       4 8 10
    E                   4       1 8
    F                   8 1       2
    Z 33       27 10 8 2      

    Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

    15) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А 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 (при условии, что передвигаться можно только по построенным дорогам).

    16) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

    Укажите схему, соответствующую таблице.

         А B C D E
    A       1 1 2 3
    B 1                   5
    C 1             2      
    D 2       2       4
    E 3 5       4      

    17) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

         А B C D E
    A       2 5 1      
    B 2       1            
    C 5 1       3 2
    D 1       3            
    E             2            

    Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

    Задания взяты из базы данных ФИПИ, сайта К.Полякова или придуманы мною