Finding the shortest path with possibility of removing an edge

[KnowledgeSeeker]

I was wondering if I can modify Dijkstra’a Alghorithm in this way: Let’s say there are 2 paths between two vertices with following lengths:

5, 8, 6, 9 // sum=28
2, 4, 8, 25 //sum=39

First path is shorter but after ignoring the longest edge in both I get the following sums: 19 and 14, so I choose the second path.

[dhayden]

Look at the proof of Dijkstra's algorithm and see what happens when you make this change. Consider pathological cases, or trivial cases.

Consider also that if you remove the longest edge, you may also be removing the shortest path between two other nodes, which would throw the entire algorithm into disarray.

[MiiNiPaa]

You need to use a function object representing sum of all edges so far. Also it would store longest edge so far and substract its value when sum is requested.

[ne555]

let me see if understand.
you've got a teletransporter that would make the distance between two points equal to 0 (if the points are connected), but you can only use it once.

solve `n' dijkstra, each one with a different teleport node