Graph Algorithms - jgoffeney/Cesium4Unreal GitHub Wiki

Back

• Wikipedia

The standard method of Dijkstra builds a graph a node at a time by keeping track of the node with the current smallest cost back to the source. That node is added to the graph. The path cost's of its children are computed, added to the queue (if they are not already part of the graph) and then again the node with the smallest cost is picked and the cycle repeats until all nodes have been added to the graph.

The Delta Stepping method differs in that rather than updating the graph based the node with the current minimum path cost from the source, it looks at a bucket of nodes which all have the current minimum source path costs within a value of delta. It further prioritizes the children of these nodes based on being light or heavy which means the edge weight from a parent to its child is less than or equal to delta (light) or greater than delta (heavy).

The algorithm sorts the current path distance costs into buckets B of size delta and each major iteration will examine the non-empty bucket with the least distance costs. Within the inner iteration the nodes within the bucket performs relaxation on the children with light edges with nodes while heavy edges are added to a temporary container R. The current bucket is then set to empty. However, during the relaxation step child nodes are sorted into buckets if their path costs are updated. This means some child nodes will be added into the current bucket. The inner loop will repeat until it is empty.

After the inner loops are complete as the current bucket is empty then all the heavy edges in R are relaxed. The child nodes will possibly be sorted into B and then the next outer loop proceeds until B is empty. Note: the heavy edge nodes that fall into the current bucket are not reconsidered until the next outer loop.

A difference from Dijkstra is for the original algorithm once a node is added to the graph it is considered complete because its current path cost is guaranteed to be the least path cost. For the Delta Stepping method this guarantee does not exist so any nodes may be reprocessed until the relaxation stage no longer finds any new lesser path costs.

The parallelization comes from relaxing all the light edges found during an inner loop concurrently.

tent : the array of the current cost from the source for each node delta: acts as the size for each bucket and to determine is an edge weight is "light" or "heavy" B: the array of buckets R: a temporary set of nodes

• Set all elements of tent to inf as all nodes have indeterminant path costs at this point.

• getPathCost(node parent, node child): float:

  • return tent[parent] + edgeCost(parent, child)

• isEdgeLight(node u, node v, float delta) : bool

  • return true if the edge cost of u to v is less than or equal to delta

• findRequests(set nodeBucket, int lightOrHeavy, float delta): set<pair<node, float> >

  • for each node parent in the nodeBucket:
    • for each node child of parent:
    • if lightOrHeavy is light and isEdgeLight(parent, child, delta):
      • create a pair of the child node v and its path cost through

• relax(node currentNode, float costThroughParent)

  • If the current value of costThroughParent is less then the value of tent[currentNode]:
    • Remove currentNode from its current bucket in B
    • Add currentNode to its new bucket
    • Set tent[currentNode] to cost

• relaxRequests(set(node) requests) *