# Single Source Shortest Paths

##### Source Code on GitHub #

The 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 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 continues until nothing can be updated. Now, we use GE to implement this algorithm.

```
Cell Struct SSSPCell
{
int distance;
long parent;
List<long> neighbors;
}
```

We first define a cell struct *SSSPCell* in TSL for this problem. The *SSSPCell*
has an integer field *distance* that holds the current shortest 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. To trace the path, we need a pointer pointing to its
*parent* vertex through which the current vertex has the shortest distance to
the source vertex. Using the *parent* pointer, we can trace back to the source
vertex from the current vertex. The field *neighbors* stores the cell ids of its
neighbors.

```
struct StartSSSPMessage
{
long root;
}
struct DistanceUpdatingMessage
{
long senderId;
int distance;
List<long> recipients;
}
```

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, the 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
protocols are 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 overriding the generated
*SSSPServerBase*.

```
class SSSPServerImpl : 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,
cell.distance, sorter.GetCellRecipientList(i));
Global.CloudStorage.DistanceUpdatingToSSSPServer(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, 0, sorter.GetCellRecipientList(i));
Global.CloudStorage.DistanceUpdatingToSSSPServer(i, msg);
}
}
}
}
}
```

The key logic in the sample code shown above is truly 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.
```