#
20 Jul 2015
Remaking Tradewars - Part IV

Shortest Path Search

### Shortest Path

In the previous post, we generated a fully-connected graph of the universe that looks something like this.

Great, we have a fully connected graph!

In Tradewars, the goal is to travel from sector to sector, buying and selling goods. Some sectors might sell cheap Fuel, while others are willing to pay top dollar for Fuel. In that case, it would be wise to keep both sectors in mind for future reference. Next time you buy cheap fuel at Sector A, you can turn around and sell it at a high price at Sector B!

To make it slightly easier to travel from sector to sector, Tradewars offers a `jump`

command, whereupon it spits out the shortest path between Sector A and Sector B, then automatically pushes you along that path, pausing in each sector to give you time to stop the jump if you see something interesting. Incidentally, this is also a great way to explore the universe!

The first obstacle in the `jump`

command is finding the shortest path. There are a lot of ways to do this, but for now, we'll use something called Dijkstra's Algorithm. It's probably one of the better ways to find the shortest path in a graph like our universe, and it's relatively quick, too.

Here's the algorithm in pseudo-code, brazenly stolen from Wikipedia:

```
function Dijkstra(Graph, source):
dist[source] ← 0 // Distance from source to source
prev[source] ← undefined // Previous node in optimal path initialization
for each vertex v in Graph: // Initialization
if v ≠ source: // Where v has not yet been removed from Q (unvisited nodes)
dist[v] ← infinity // Unknown distance function from source to v
prev[v] ← undefined // Previous node in optimal path from source
end if
add v to Q // All nodes initially in Q (unvisited nodes)
end for
while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q
for each neighbor v of u: // where v is still in Q.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
end if
end for
end while
return dist[], prev[]
end function
```

In graphical form, it looks something like this (also stolen from Wikipedia):

There are some other variants of this, and I leave it as an experiment to the reader to try them out.

By passing in our Universe as the `Graph`

, and the starting sector as the `source`

, we can find all of the paths available. Finding the shortest path to a particular target is a matter of choosing the `target`

item from the resulting `dist[]`

that is returned from the function.

Tune in for Part V, when we talk about the next exciting module in Tradewars: outposts.

-B