Sample algorithm to "linearize" a graph

Simplifying a business example, I have the following situation:

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

Say, a voyager visits some cities. Several cities are visited multiple times.

So, we have list of cities in ordinate axis (that may be duplicated), and Time in abscissas one.

Now, for a given path, say (A => X => A => B => C) we should display a line, in the "most linear way possible".

By eg. in the image above, the green line is optimal one

(1 > 2 > 3 > 4 > 5)

but there could be multiple possible outputs

(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)

Is there some algorithms helping in such sit开发者_如何学JAVAuations?

---

Construct a graph where a node is a pairing of city+value and time (e.g. A(3)/1). An edge exists between two nodes that are adjacent in the path (e.g. A(3)/1 to X(2)/2).

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

Example graph (edges given in degrees and are 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