Multiple reference point shortest path algorithm

A non-transitory, computer-readable medium storing instructions operable when executed to cause at least one processor to perform operations for determining, in directed graph data maintained in a distributed computing system and describing a directed graph that includes a plurality of vertices for which processing is performed in parallel in a series of synchronized iterations, shortest distances between a source vertex and other vertices from the plurality of vertices, the directed graph data including one or more reference vertices from the plurality of vertices, the operations comprising:

• receiving, at a particular vertex from the plurality of vertices, an update message indicating a distance between the particular vertex and a particular remote vertex, wherein a remote vertex comprises a source vertex or a reference vertex;
• in response to receiving the update message, updating a distance value for the particular vertex indicating a distance from the particular vertex to the particular remote vertex;
• determining that the particular vertex is a reference vertex and that the particular remote vertex is the source vertex;
• in response to determining that the particular vertex is a reference vertex and that the particular remote vertex is the source vertex, sending a global update message including the updated distance value to at least a two or more of the plurality of vertices in the directed graph data.

A system comprising:

• one or more computers;
• and
• one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations for determining, in directed graph data maintained in a distributed computing system and describing a directed graph and that includes including a plurality of vertices for which processing is performed in parallel in a series of synchronized iterations, shortest distances between a source vertex and other vertices from the plurality of vertices, the directed graph data including one or more reference vertices from the plurality of vertices, the operations comprising:
• receiving, at a particular vertex from the plurality of vertices, an update message indicating a distance between the particular vertex and a particular remote vertex, wherein a remote vertex comprises a source vertex or a reference vertex;
• in response to receiving the update message, updating a distance value for the particular vertex indicating a distance from the particular vertex to the particular remote vertex;
• determining that the particular vertex is a reference vertex and that the particular remote vertex is the source vertex;
• in response to determining that the particular vertex is a reference vertex and that the particular remote vertex is the source vertex, sending a global update message including the updated distance value to at least a two or more of the plurality of vertices in the directed graph data.