Single source shortest path resolution

摘要

Techniques for resolving single source shortest path for database processing are provided. Graph data for nodes having weights for edges of a database network are iterated producing a new message table and results table in each iteration. The results table stores the minimum path weight. For each iteration the graph data and message table are joined to produce a state of a node and outgoing edge messages. The message table and results table are co-grouped to generate a new message for a next node to process. When done the single source shortest path for the network is produced.

主权项

1. A method implemented and programmed within a non-transitory computer-readable storage medium and processed by a processing node (node), the node configured to execute the method, comprising:
acquiring, at the node, a starting message table that represents an identifier for a vertex processing node of a graph of a network of processing nodes and the starting message table representing a distance from a source node to that vertex within the network; joining, at the node, graph data and the starting message table to calculate a state of the node and outgoing edge messages for the graph data, wherein the graph data includes a beginning vertex of an edge in the graph and an ending vertex of an edge in the graph; grouping, at the node, the messages; cogrouping, at the node, the starting message table and a result table to generate new messages in a new message table, and wherein the result table including a destination vertex from the graph and a minimum distance from the source node to a current vertex; replacing, at the node, the message table with the new message table and producing a shortest path from the source node within the network to a destination node as the new message table for network path traversal of network communications; and passing, from the node, the new message table to a next node represented in the graph data.