# Single Source Shortest Paths

##### Source Code on GitHub #

Vertex centric graph computation model provides an intuitive way of computing single source shortest paths. Each vertex maintains its current distance to the source vertex. Once a vertex's distance is updated, it sends out its current shortest distance to its adjacent vertices. When a vertex receives the shortest distances from its neighbors, it re-calculates its shortest distance to the source vertex. The process will continue until nothing can be updated. In the following, we use GE to model and implement this algorithm for calculating single source shortest paths.

We first define a cell struct for this problem. First of all, we
define a *distance* field to hold the current shortest distance to the
source vertex. To trace the path, we need a pointer pointing to its
*parent* vertex from which it gets its latest shortest distance. Using
the *parent* pointer, we can trace back to the source vertex from the
current vertex.

```
Cell Struct SSSPCell
{
int distance;
long parent;
List<long> neighbors;
}
struct StartSSSPMessage
{
long root;
}
struct DistanceUpdatingMessage
{
long senderId;
int distance;
List<long> recipients;
}
```

As shown in the tsl script shown above, the *SSSPCell* has an integer
field *distance* indicating its distance to the source vertex. We will
initially set it to the maximum positive value of 32-bit integer. The
second field *parent* is the cell id of the vertex from which the
shortest path is routed. The field *neighbors* stores the cell ids of
its neighbors.

Now we define two types of messages for the computation:
*StartSSSPMessage* and *DistanceUpdatingMessage*. *StartSSSPMessage*
is used to initialize an SSSP computation. It is a simple struct
containing only the cell id of the source vertex. A GE
client can kick off the computation by sending a *StartSSSPMessage* to
all GE servers. Receiving this message, servers will check
whether the specified source vertex is in its *LocalStorage*. If this
is the case, it will load the source vertex's adjacent vertices and
propagates *DistanceUpdatingMessages* to its neighbors. On receiving a
*DistanceUpdatingMessage*, a vertex will check whether its distance
can be updated according to the received shortest distance. The
corresponding tsl script is shown below.

```
protocol StartSSSP
{
Type: Asyn;
Request: StartSSSPMessage;
Response: void;
}
protocol DistanceUpdating
{
Type: Asyn;
Request: DistanceUpdatingMessage;
Response: void;
}
server SSSPServer
{
protocol StartSSSP;
protocol DistanceUpdating;
}
```

The message handling logic can be implemented by override the
generated *SSSPServerBase*.

```
class SSSPServer : SSSPServerBase
{
public override void DistanceUpdatingHandler(DistanceUpdatingMessageReader
request)
{
List<DistanceUpdatingMessage> DistanceUpdatingMessageList =
new List<DistanceUpdatingMessage>();
request.recipients.ForEach((cellId) =>
{
using (var cell = Global.LocalStorage.UseSSSPCell(cellId))
{
if (cell.distance > request.distance + 1)
{
cell.distance = request.distance + 1;
cell.parent = request.senderId;
Console.Write(cell.distance + " ");
MessageSorter sorter = new MessageSorter(cell.neighbors);
for (int i = 0; i < Global.ServerCount; i++)
{
DistanceUpdatingMessageWriter msg =
new DistanceUpdatingMessageWriter(cell.CellID.Value,
cell.distance, sorter.GetCellRecipientList(i));
Global.CloudStorage.DistanceUpdatingToServer(i, msg);
}
}
}
});
}
public override void StartSSSPHandler(StartSSSPMessageReader request)
{
if (Global.CloudStorage.IsLocalCell(request.root))
{
using (var rootCell = Global.LocalStorage.UseSSSPCell(request.root))
{
rootCell.distance = 0;
rootCell.parent = -1;
MessageSorter sorter = new MessageSorter(rootCell.neighbors);
for (int i = 0; i < Global.ServerCount; i++)
{
DistanceUpdatingMessageWriter msg = new
DistanceUpdatingMessageWriter(rootCell.CellID.Value, 0,
sorter.GetCellRecipientList(i));
Global.CloudStorage.DistanceUpdatingToServer(i, msg);
}
}
}
}
}
```

The key logic in the sample code shown above is very simple:

```
if (cell.distance > request.distance + 1)
{
cell.distance = request.distance + 1;
cell.parent = request.senderId;
}
```

We can try out the example by following the steps shown below:

Generate a testing graph using

`SSSP.exe -g NumberOfVertices`

. For example,`SSSP.exe -g 10000`

.Start computing each vertex's shortest distance to the specified source vertex by

`SSSP.exe -c SourceVertexId`

. For example,`SSSP.exe -c 1`

.Get the shortest path between a specified vertex and the source vertex by

`SSSP.exe -q VertexId`

. For example,`SSSP.exe -q 123`

.

A sample output of executing `SSSP.exe -q 123`

:

```
Current vertex is 123, the distance to the source vertex is 3.
Current vertex is 1001, the distance to the source vertex is 2.
Current vertex is 2432, the distance to the source vertex is 1.
Current vertex is 1, the distance to the source vertex is 0.
```