A faster algorithm than dijkstra's algorithm

[demonwolf]

I'm trying to solve a variation on the shortest route finding problem.
The mazes have n intersections with m corridors. Each corridor has two intersections.
In my case the mazes have a start point (at node 0) and an end point (at node n-1).

As you traverse every corridor you get hit by a factor f changing your size.
The program should work out the best outcome where you are the biggest size after making your way to the end point.

The data is given as such

n m
start Node - end Node - factor in corridor

An example data set is given below

3 3
0 1 0.9
1 2 0.9
0 2 0.8

This gives information of a maze with three nodes and three corridors.
there is a corridor between node 0 and 1 and you get hit by a factor of 0.9
there is a corridor between node 1 and 2 and you get hit by a factor of 0.9
there is a corridor between node 0 and 2 and you get hit by a factor of 0.8

In this case the best possible size is 0.81 i.e. 0.9*0.9

The number of nodes can be between 2 and 10000
and the number of corridors can be between 1 and 15000

I've assumed the possibility that the factors can be the same for different corridors.

I've solved the problem using a modified dijkstra's algorithm. Where initially node 0 has a weight of 1 and the rest of the nodes have a weight of 0.
I calculate the weight at each node by multiplying the 'cost' (factor) by the adjoining nodes weight.

I construct a second array of the weight of each node which I search to find the highest current weight that hasn't been selected before:

MY pseudo-code:

select node 0
do
{
iterate 0 -> m
calculate the weight of each node connected to the selected node
if weight is greater than weight of node change to highest weight

iterate 0 - > n
find a node with the highest weight and has not been selected before
select node
}
while (selected node is not the last node)

return the weight of the last node.


I've submitted this solution to an automated system and have received the response that it was too slow. That the accepted solution is faster.
I've tried to find a faster solution but cannot see it.
I've optimised my code with index arrays to only partially search all the corridors yet that is still too slow.

Can someone point me in the direction of a faster solution? I'm curious to know what the accepted solution might be and can't seem to leave the problem alone until I solve it.