I wish I knew the correct terminology for the question that I would like to ask, but I don't, so please forgive me if I am not calling the right things by the right names. The practical problem that I am trying to solve (and whose specific nature is to do with data compression) can be phrased as follows:

We have a directed graph with a number of parallel edges with positive weights. So, I am guessing that this might be called a directed weighted multigraph. I need to construct a shortest path on this multigraph, but I cannot use any standard algorithms for it because my graph also happens to be dynamic.

Now, when I tried searching academic literature on dynamic multigraphs, they usually talk about the graphs where you have to be able to reconstruct your shortest path as you follow it, e.g. maybe for realtime traffic navigation. My graph is different in that it does not change due to an external factor. However, it changes every time when particular edge is selected to be a part of the shortest path. So it is as if once you choose edge 1 from node A to B for your shortest path/spanning tree, you disable edges 3-5 from node B to other nodes. So, the graph is changing as the direct result of our traversal.

I am hoping that this kind of dynamic graph problem can have another name, so that I can try to find some academic literature on how one can attack problems of this kind. Or, maybe there is a standard way of recasting this type of problems that makes them more aminable to the efficient computation. Basically, I would appreciate any pointers on how I can try dealing with something like this efficiently, i.e. without setting up direct brute-force iteration through all possible options.

  • 1
    $\begingroup$ I don't think the question is answerable without knowing what the new weight of an edge depends on, when it changes. Every time you select one edge, the entire graph changes? (Or all the weights change, but not the structure of the graph?) What can the new graph / new weights depend on? The entire path chosen so far? Just which edge was most recently selected? The previous weights? Something more limited? It sounds like this is a non-standard situation, so the more you can tell us about that dependence, the more likely that we can suggest a method that might be suitable. $\endgroup$ – D.W. Mar 22 '18 at 16:11
  • 1
    $\begingroup$ In the general case (where the new weights can depend on anything & everything), this probably won't be solvable except through brute force. So the more limited the dependence, the greater the hope for efficient algorithms. $\endgroup$ – D.W. Mar 22 '18 at 16:12
  • $\begingroup$ Got you. Hmm. Basically, it is a bit like having an internal state during movement along the path. So, picking a particular edge usually means commiting to a specific internal state, which adds weight to some edges and removes weight from some other edges. I'll think a bit and will try to come up with a more specific, possibly visual explanation. $\endgroup$ – introspec Mar 22 '18 at 16:22
  • $\begingroup$ So the choice of edge affects the internal state. OK. Now, what effect does the internal state have on the graph? Does it have an arbitrary effect on the entire graph? An arbitrary effect on all edge weights? Should I infer that the weight of every edge is a function of the internal state? How large is the space of possible internal states? $\endgroup$ – D.W. Mar 22 '18 at 17:23

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.