Find a minimum distance with a number of even green edges

Admin 1
Viewed 446

Hi I'm a computer science student, in my second year. During my studies, I got stuck with a question I couldn't solve, a question I was exposed to in order to expand my knowledge. Question: There is an undirect graph, with edges of positive weight, I have to find I am the minimum distance between, in addition The graph has 2 types of edges - blue and green. I need to find a minimum distance between and also the number of its green edges in the tree is even.

enter image description here

I was thinking of an algorithm based on the Dijkstra algorithm. Let's start from s Each time we go to the bow with the minimum number. If we have to go to a green vertex - right after that we try to go - to another green vertex.

enter image description here

I tried to draw my idea but it didn't work properly.

Why doesn't my idea work properly? what am I missing? Thanks for the help.

dijkstra algorithm
1 Answers

I would construct a new graph.

For each vertex i in the original graph, construct two vertices in the new graph numbered 2i and 2i+1.

For each blue edge i to j, construct edges 2i to 2j and 2i+1 to 2j+1. For each green edge i to j, construct edges 2i to 2j+1 and 2i+1 to 2j.

Then Dijkstra's algorithm on the new graph from 2i to 2j will tell you the shortest distance from vertex i to j with an even number of green edges. (2i to 2j+1 will tell the shortest distance with an odd number of green edges.)

The idea is that we switch from the even graph to the odd graph whenever we traverse a green edge.

Your idea sounds like it only considers paths with two consecutive green edges. This will probably work for some graphs, but not all as in some case the optimum route may not include consecutive green edges.

UPDATE

For the graph in your comment:

enter image description here

the new graph looks like:

enter image description here

user_11393930
Related