I have an undirected graph with weighted edges, in which I want to find the shortest paths from an initial node to every other node. Obviously Dijkstra's algorithm is usually a good choice, and I have previously used the variant where a min-priority queue (heap) is used to keep the set of tentative nodes $N_T$, and nodes are only added to $N_T$ as they are discovered.

However in this problem edge weights are dynamic. Each edge has a weight $w_{ab}=d_{ab}\gamma_b$, where $d_{ab}$ is the constant distance between nodes $a$ and $b$, and $\gamma_b$ is a dynamic scaling factor. $\gamma$ is first defined when a node is added to the tentative set, and it is fixed when a node is marked as visited. But while a node remains in the tentative set, $\gamma$ can change depending on the nodes visited in other parts of the graph. These non-local changes make it difficult to maintain the queue, since an addition of a new node may cause the weights to change and require the whole queue to be re-sorted.

If it helps: the tentative nodes are in groups, and nodes within a group will change weights uniformly - although groups can sometimes split and merge. So in fact the edge weight is $w_{ab}=d_{ab}\gamma_g$, where $g$ is the tentative node's group.

enter image description here Illustration of groups during graph traversal from node $n_0$. At first there are two $\gamma$ groups, $g_x$ and $g_y$. Later, they merge into one group, $g_z$. $\gamma$ is constant within each coloured rectangle. The dashed lines show the tentative node set at various times during execution.

What is the most efficient way to manage the group of tentative nodes, given that the edge weights may change? I am open to other ways to tackle the problem, e.g. run Dijkstra's algorithm in multiple passes, only updating $\gamma$ after each pass.

In terms of problem size, the graph is sparse and there are on the order of:

  • $\lvert{N}\rvert\approx100k$ nodes
  • $\lvert{N_T}\rvert\approx1000$ nodes in the tentative set
  • $\lvert{G}\rvert<\lvert{N_T}\rvert$ $\gamma$ groups

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.