the exercise:
in undirected graph vertices have can have weights in addition to the weights of edges
This problem is to write algorithem that finding the cheapest path between vertices a and b in a graph G.
The cost of a path is the sum of the costs of the edges and vertices encountered on the path.
to make it more simple to understand let's think on it as: vertex is a city, the edges is the road between cities.
where we can think on the weights as the following:
the weight of the vertexes is waiting time at a traffic light right before entering the city, and the edge weight is the time to get to that traffic light(if there is any).
my first approach was to add the weight of each vertex to all edges its connected to and then run dijkstra, but this is wrong, for example: graph image
as you can see the shortest path from the "red city" to the "green city" is the lower path (cost of 11)
but if we use this approach then we will get this new graph where the shortest path is the upper.
my second approach which i think will work is to create new graph so for each undirected edge (u,v) in the original graph, add two edges in the new graph we created: (u,v) such that w'(u,v)=w(v) and (v,u) such that w'(v,u)=w(u). then we get directed graph and we can run dijkstra on it. if we look at the example from before we will get this graph
is this correct? is there any simpler solution to this?
as for time complexity according to wikipedia when using Fibonacci Heap (that i didnt learn yet) the total cost it O(E+V log V) but what will be the time complexity for building the directed graph? and if i want to show\prove the correctness is it enough to say because the correctness of dijkstra?
The approach with the directed graph is correct. In the original graph the cost related to travelling from one city to a next city is comprised of the cost of the edge and the cost of the target city. So if you combine those costs in a directed edge, and remove the concept of costs at vertices, you have the same costs of travelling, and thus the solution of Dijkstra's algorithm will be the one you need for the original graph as well.
The time complexity to create this derived graph is equal to O(𝑉+𝐸), as all vertices and all edges have to be created, and the time needed to calculate the cost is constant per edge. This time complexity is better than the time complexity of Dijkstra's algorithm, so the graph construction step doesn't negatively affect it.
