Бағытталмаған салмақты граф қабырғаларының салмақтары бар тізімімен берілген: A–B: 4, A–C: 2, B–C: 1, B–D: 5, C–D: 8, C–E: 10, D–E: 2, D–F: 6, E–F: 3. A төбесінен F төбесіне дейінгі жолдың ең кіші жиынтық ұзындығы неге тең?
Жауап пен талдауды көрсетуЖауап пен талдауды жасыру
Дұрыс жауап
- A13
Талдау
Дейкстра алгоритмін қолданамыз. A төбесінен C төбесіне дейін 2, B төбесіне дейін 4. C арқылы B төбесіне 2 + 1 = 3, бұл 4-тен тиімді, сондықтан B = 3. D төбесіне B арқылы 3 + 5 = 8, C арқылы 2 + 8 = 10, яғни D = 8. E төбесіне D арқылы 8 + 2 = 10, C арқылы 2 + 10 = 12, яғни E = 10. F төбесіне E арқылы 10 + 3 = 13, D арқылы 8 + 6 = 14, яғни F = 13. A–C–B–D–E–F ең қысқа жолының ұзындығы 13. «14» жауабы A–C–B–D–F жолынан, «15» жауабы A–B–D–F жолынан, «18» жауабы A–B–C–E–F жолынан шығады.