CODEWITHSUNDEEP
algorithmgraph
xiaodelaoshi
xiaodelaoshi

Reputation: 631

How to find the longest step in a path in a graph

I have a question about this scenario, say give you a list of vertexes and everyone of them are connected with the weight as its distance between each, now instead to find its shortest distance(because everyone is connected, shortest path is trivial), I wish to have a path that the maximum distance between adjacent vertexs, is minimized. for example we have 4 vertexes in position:

A:(0, 0), B (20, 0), C(5, 5), D(15, 5)

The goal is from A to B and the path should be A-->C-->D-->B, while it is not the shortest path, but the longest step is 10(C-->D) is smaller than A-->B which is 20, is there any algorithm can find such path and return the maximal step in this path?

Upvotes: 1

Views: 61

Answers (2)

mcdowella
mcdowella

Reputation: 19621

Just because everything is connected to everything else in your original problem doesn't mean that you can't set up and solve problems where only some edges exist. If you keep only the edges of length at most K and still find a path from A to B you know that there is a path from A to B with the longest edge at most K. If you fail to find such a path, you know there is no such path.

So by running a binary search you can find the smallest K such that there is a path from A to B using edges of length at most K, but no path from A to B using only edges of length shorter than K. This value of K is the maximum step distance on your path, and you can find where it is by taking the path from A to B and looking at the lengths of its edges (of course you might find two edges on the path with length exactly K).

Upvotes: 1

Silver
Silver

Reputation: 29

I think it is not clear about what your goal is, but might be you need to have a deep research about heuristic algorithm.

Upvotes: 0

Related Questions