🔢 Графы и алгоритм Дейкстры #математикаграф #математика
Представим себе, что у нас есть граф. А что такое граф? Это значит, что есть какие-то вершины, и эти вершины как-то соединены рёбрами. Какие-то вершины могут быть соединены, какие-то — нет.
Можете для простоты представлять себе, что вершина — это некий перекрёсток. Ну, а между перекрёстками протянуты улицы, которые соединяют эти перекрёстки, или, если вам так проще, города, которые соединены авиалиниями. Всё это примеры графов.
У каждого ребра есть свой вес. Весом может быть что угодно. В случае с нашим графом улицами это может быть длина этой самой улицы или время, за которое автомобиль проедет. Да, если мы говорим про задачу, которую решает наш навигатор — за кратчайшее время.
Если мы перевели задачу в сторону навигатора проехать из одной точки в другую, в случае с графом нам нужно найти кратчайший путь по этим рёбрам, учитывая веса соответствующих рёбер. Разумеется, просто перебор всех возможных путей — это совсем не оптимально.
А так или иначе, эти алгоритмы есть. Вот про алгоритм Дейкстры я сейчас и поговорю.