CODEWITHSUNDEEP
graph-theorydijkstra
Louie Holbrook
Louie Holbrook

Reputation: 31

How to find the best fit path

I have a set X of ordered weightings e.g. [2, 8, 5, 13, 1].

I am given a graph with edges of various weights. Example graph

Given a start node, which algorithm should be used to find the path such that the weightings of the path are best fit with the weightings of set X?

Is there a smarter way of doing it bar iterating over every possible path of length length(set X) and seeing which one is best fit?

What do I mean by 'best fit'? In my mind it means that the overall absolute difference between the weights of the edges of the path and the corresponding weights of set X will be as small as possible.

Upvotes: 0

Views: 101

Answers (1)

Celelibi
Celelibi

Reputation: 1501

First, if the order of the list of weights is important, then it's a list, not a set.

You could use a best-first search. Just not directly in your given graph, but in a graph you'll build from it. I'm gonna assume the graph is directed. If not, just make the edges both ways.

Let's call N the length of your list X. Then, let's define N replicates of your input graph G[0], G[1], ... G[N-1].

Then, let's define the weights of the edges in G[i] such that it corresponds to the cost of matching X[i] (the i-th weight) to that edge. So basically, if in the initial graph G an edge had the weight w, then in G[i] it will have a cost |w-X[i]|.

Finally, connect the graphs G[i] to G[i+1] (the next graph) such that when a weight of X has been matched, we move up one graph. So basically, if we have an edge (v1[i], v2[i]) in the graph G[i] with weight w, now we move it so that we have an edge (v1[i], v2[i+1]) with the same weight w. Essentially, instead of staying on the same level, we move up level up.

In this new graph you can apply you usual shortest-path algorithms. Including Dijkstra since all your weights are non-negative. The complexity is bounded by that of your choosen shortest path algorithm in a graph N times larger.

But note that you don't have to explicitely represent the N replicates of the graph. Especially since you may have noticed that a good chunk of your new graph cannot be used at all. You could simply consider your graph implicitly by representing the nodes by the pair (V, i) with V a node in the original graph, and i the current position in your weight list X.

You could replace your notion of best fit by whatever you want as long as it ends up as a sum along the path. And you can use Dijkstra only as long as you don't generate negative edge weights.

Upvotes: 1

Related Questions