Example algorithm for linearizing a graph

Question

To simplify the business example, I have the following situation:

Some objects should be distributed on the graph in the most "linear" way for a given "thermometer".

Say a traveler visits some cities. Several cities are visited several times.

So, we have a list of cities along the ordinate (which can be duplicated), and time - on the abscissa.

Now, for this path, say (A => X => A => B => C) , we need to display the line in the “most linear way”.

E.g. In the image above, the green line is optimal. (1> 2> 3> 4> 5)

but there may be several possible solutions

(1> 2> 1> 4> 5)
(1> 2> 3> 4> 5)
(1> 2> 6> 4> 5)

(3> 2> 1> 4> 5)
(3> 2> 3> 4> 5)
(3> 2> 6> 4> 5)

(6> 2> 1> 4> 5)
(6> 2> 3> 4> 5)
(6> 2> 6> 4> 5)

Are there any algorithms that help in such situations?

Answer 1

Build a graph where a node is a pairing of the city + value and time (for example, A (3) / 1). An edge exists between two nodes that are adjacent along the path (for example, A (3) / 1 to X (2) / 2).

The edge weight will be the difference in vector (opposite angle) between the last pair of nodes and the next pair of nodes (this will make the dynamic weight of the edge depending on where it came from). Then use the Dijkstra to find the minimum distance to the target (a).

Graph example (edges set in degrees and just estimates):

Total cost 0 0 105 15 A31 -> X22 -> A13 -> B44 -> C55 120 90 0 0 -> A33 -> B44 -> C55 90 115 110 105 -> A63 -> B44 -> C55 330