# Shortest path problem in ring buffer or circular double linked list

Shortest path problems are everywhere with many algorithms and since I haven’t (yet) found an algorithm for this particular one, well, here we go!

## Clockwise or counterclockwise?

A friend of mine was developing a microcontroller’s software and faced a particular shortest path problem: the microcontroller had to activate a stepper motor to turn a disk from the current position A to the desired position B. The number of positions of the disk was fixed and predetermined, just like the hours on an analogical clock. There are of course two possible paths: clockwise and counterclockwise. But which is the shortest?

An example to understand better the problem:

Think about an analogical clock and ignore the minute and second hand. Your hour hand is currently pointing to

`11`

and you want to move it to`3`

. Do you turn the hand clockwise or counterclockwise?

Easy to say, when you are human and visualize the clock/ring, right? But what about a computer?

## Problem hypotheses

- We are working on a
**circular bidirectional ring-like data structure**(like in the image below), where the*next*of the last element is the first and vice-versa. - The ring is divided in
**finite equal parts**, like in the cover picture or like on an clock. - The ring parts are
**enumerated sequentially starting from 0**. A start from 1 is also possible. - The
**current position**(part of the ring), the**desired position**(part of the ring) and the**circumference**of the ring (which is the number of ring parts) are known*a priori.*

## Algorithm in C

All the following source code forms are subject to the terms of the BSD 3-Clause license.

### Oriented arc

To travel along a ring we need a displacement vector, that is something that
gives us the *length* of the path we need to travel and in which *direction* we
have to move. A representation of this vector may be an oriented arc of the
ring. Let’s make it as a C struct:

```
#include <stdbool.h> /* Allows usage of booleans */
#include <stdlib.h> /* Allows usage of abs() */
struct oriented_arc_struct {
int length;
bool clockwise;
};
typedef struct oriented_arc_struct oriented_arc;
```

The length is expressed as the number of steps to perform, that is the parts of
the ring we need to visit. The direction is expressed as a boolean, which is
`true`

if we move clockwise, else `false`

. To use booleans we need the
`stdbool.h`

library first. We also add `stdlib.h`

for the absolute value
function `abs()`

used in the next part. This struct could have been done with an
array of two integers, but I’ve chosen this way since it’s more adaptable to
longs or even doubles while being more readable.

### Minimum path

The function that returns the shortest oriented arc between two points on a ring is the following. Note that the function that finds the shortest path is independent of the exact implementation of the structure. The computation is performed on index level.

```
oriented_arc min_oriented_arc(int circumference, int start_point, int end_point) {
int distance_1 = end_point - start_point;
oriented_arc arc_1 = {abs(distance_1), (distance_1 >= 0) ? true : false};
oriented_arc arc_2 = {circumference - abs(distance_1), !arc_1.clockwise};
if (arc_1.lenght <= arc_2.lenght) {
return arc_1;
} else {
return arc_2;
}
}
```

Let’s break it down: between two points on a ring there are two arcs, where
usually one is shorter or they are equal. To calculate the first one we
calculate `distance_1`

first. If it is negative, then we are moving
counterclockwise and we save `false`

in `arc_1.clockwise`

. As `arc_1.length`

we
put the absolute value of the calculated distance (basically it’s the taxi-cab
distance).

The second arc, `arc_2`

, is of course complementary to `arc_1`

, which means has
complementary length and opposite orientation. Of the two arcs, we return the
one with the shortest length or the first one if they are equal.

Note that the orientation for a movement of 0 length (from `start_point`

to
`start_point`

) has clockwise orientation. On the other hand the orientation of
the arc with the complementary with same length may be clockwise or not,
depending on the `start_point`

and `end_point`

, but it doesn’t matter since the
length of the path is the same in both directions (circumference/2).

### Full program with example path computations

Here is the whole C code with example computations performed for a 12-part ring, like the clock.

## Abstract data structures with this shortest path need: *Sequentially sorted circular double linked list*

I know, the title looks scary, but I’ll explain it gradually. This is an example
of what kind of abstract data structure may need this shortest path algorithm to
find the necessary data faster. You know, theory stuff - and **it is not needed
to understand and use the algorithm.**

Also probably the structure is not optimized in many ways, since and array or,
even better, a **hash table would
solve the problem faster and nicer**, but it can be an abstract representation
of a physical constraint - like moving the hour hand of the clock.

Circular structures like the numbers of the clock or the cover image may be
created in many ways in software. One is called
circular buffer (or ring), is
usually based on an array or a
dynamic array (a.k.a. arraylist)
and used for other purposes. A great advantage of arrays and dynamic arrays is
the random access. Imagine you
are in position 11 and want to reach position 3: just type `my_array[3]`

and
you’re done, but this is not our case. Think again about the clock: **you are
not able to “just jump”** to another position with the hour hand, but you need
to travel along a path step by step.

Now let’s imagine that our array has no random access, but only
sequential: from my current
position I can reach only the next one and from that the next one and so
on. Linked lists are an example of
that. We can then make the list *bidirectional* or *double,* as usually
called. On a structure like this, we are allowed to move in two directions,
*left* or *right* as on the *Image 1*, usually referred as *next* and
*previous*.

If you add the circularity on this list (the last connects to the first and vice
versa), you’ll get a *circular double linked list* like on *Image 3*. On this
structure we may move still in two opposite directions, but it’s better to call
them *clockwise* and *counterclockwise* since *left* and *right* have no sense
on a circle (no pun intended).

Now we have the structure to represent **a ring with finite positions**
(hypotheses 1 and 2, check!). On this kind of structures we are able to reach
any point using two different paths and of course we need the shortest one.

We are still missing the third hypothesis: **sequential numbers**, just like the
numbers on our clock or the numbered disk of the microcontroller. *Image 4*
shows a structure that implements this.

Depending on the problem, just the sequential numbers on their own may be of no
use (since they give no information). To improve that, each block on the list
may point to a data block. *Example:* each number on the clock points to its
string description, so *12* points to *“Noon”*.

This is one of the possible abstract structures that satisfies the hypotheses.

*Edit 2015-04-28:* added Image 4, hypothesis (now) 1, change chapters
order and modify text to include the sequentiality of the numbers.