Найти путь в графе со взвешенными вершинами

Question

У меня есть следующий граф, где каждая вершина имеет ассоциированную "вероятность" ( граф со взвешенными узлами).

Я хочу найти путь от узла 0 до последнего узла (самый высокий индекс, здесь 5), который имеет наибольшую умноженную вероятность. На этом графике лучший путь - 0-1-4-5, что дает вероятность 0,72.

Я думал об использовании BFS, чтобы найти все пути между начальным и конечным узлами, а затем умножил вероятность для каждого узла, но я думаю, что это слишком наивный подход, чтобы работать для всех графиков. Как я мог решить это с помощью Python?

Answer 1

Как предположил Жюльен, алгоритм Дейкстры будет хорошим началом здесь. Есть две разницы между вашей проблемой и обычной Дейкстрой.

1. Алгоритм Дейкстры минимизирует сумму весов. Чтобы максимизировать произведение вероятностей, вы можете отобразить каждый вес p в -log(p), Быстрое доказательство: максимизация продукта (x1*x2*...*xn) так же, как максимизация log(x1*x2*...*xn) поскольку log монотонно увеличивается. argmax(log(x1*x2*...*xn)) = argmax(log(x1)+log(x2)+...+log(xn)) = argmin(-log(x1)-log(x2)-...-log(xn))), Обратите внимание, что если вы хотите получить полученную вероятность, вы бы изменили свой результат, взяв 10^(-c) где c это минимальная стоимость, возвращаемая Дейкстрой с использованием вышеуказанного сокращения (при условии, что вы взяли журнал с основанием 10). Отметим также, что если любые вероятности равны 0, log(0) не определено, поэтому вы должны обработать это, сделав вес бесконечным (чтобы путь никогда не проходил через этот узел).

2. Дейкстры используют взвешенные ребра, тогда как у вас есть взвешенные узлы. Но это простое сокращение от взвешенных узлов до взвешенных ребер. Определите вес ребра из u в v с edge_weight(u,v) = vertex_weight(v), Судя по вашей картинке, у вас есть неориентированный граф, поэтому вам нужно будет заменить каждое неориентированное ребро двумя направленными ребрами, используя те же веса, как описано выше (обратите внимание, что два ребра между двумя вершинами u а также v будет иметь разные веса, если vertex_weight(u) == vertex_weight(v)). Также, если вы хотите вернуть значение кратчайшего пути, вам нужно будет добавить vertex_weight(source_vertex) до конечной стоимости, так как эта стоимость пропускается при уменьшении.