Consider the minimum weight path problem on a directed graph where, instead of edges, vertices have weights. The weight of a path is the sum of the weights of the vertices on the path excluding the endpoints. The input is a directed graph with n vertices and m edges, weights \({W_v}\) for every vertex v, and a starting vertex s.
Which of the following is/are correct regarding finding the minimum weighted path on the given vertex weighted graph.
1
Dijkstra’s algorithm can be used to find the shortest path
2
The Time complexity of the above computation will be O(E + VlogV)
3
if the graph is converted into an edge-weighted graph with some modification the shortest path will remain the same.
4
if the graph is converted into an edge-weighted graph with some modification the shortest path will be different.