Eu não entendi direito porque você usa uma fila de prioridades de arestas, e não uma fila de prioridades de vértices. A idéia me parece certa, a única diferença do jeito que eu fiz é essa mesmo. A probabilidade de chegar em um vértice v usando a aresta uv é a probabilidade que eu cheguei em u vezes a probabilidade da aresta uv. Inicialmente, a fila contém o vértice inicial com probabilidade 1.
Talvez seja erro de código mesmo. Se quiser me mandar o código pelo email, posso dar uma olhada depois.
Forum