CODEWITHSUNDEEP
graphgraph-algorithm
Andrea Casaccia
Andrea Casaccia

Reputation: 4971

Graph shortest path?

I am facing which I believe is a kind of shortest path problem on a graph.

I need to find shortest path from node A to B, considering all edges have positive weight for connected vertexes, ∞ for not connected ones.

Vertexes have variable positive weightes.

The cost of a path is the weight of the vertex with maximum weight considering all vertexes involved in that path.

Should I apply Dijkstra in this situation, and if so how, considering that the weight of each Vertex changes depending on the previous vertexes visited?

Can you point me on how to tackle this problem otherwise?

Upvotes: 2

Views: 420

Answers (1)

member555
member555

Reputation: 807

I cant understand if you should consider the weights of the edges,because you said that you want the path with the max/min weight on a vertice possible,from A to B. My solution for that is to convert every weight on vertex,to a weight on edge , just like in the image:enter image description here

now you want to find the path from A to B where the the biggest weight on edge is min/max. you can use MST algotirhm for this,because you dont care about the path lenght,but only the max/min edge cost.

Upvotes: 0

Related Questions