11 ms·

Historic algorithms help unlock shortest-path problem breakthrough

• deleted 3y ago
  [deleted]
• ozarker 3y ago
  What’s an application where you’d absolutely have to have a graph with negative weights? Couldn’t you just preprocess the edges and normalize their weights?
  • bhl 3y ago
    The issue with negative weighted edges is that a cycle would result in an infinite loop when finding shortest path, compared to when all edges are non-negative, cycles can be safely skipped. Compared to Dijkstra's original algorithm of E + V log V, naively pre-processing edges would require V^2 work assuming an edge can exist between each vertex. Edit: the algorithm you’re describing exists btw https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm https://en.m.wikipedia.org/wiki/Johnson%27s_algorithm
    • schneems 3y ago
      I think the question isn’t “what is the issue with negative weights” rather “what is a real world example of negative weights” which the article doesn’t really explain. I don’t know any off hand. I would guess its when a path has a benefit incurred rather than a cost. I.e. in a monopoly board it might be shorter to get to a destination by getting thrown in jail first, but the longer path around the whole board comes with a benefit I.e. negative weight of receiving $200 by crossing the start. Your reply does help clarify the “why not normalize” which is helpful. I’m still curious for other examples of negative weights.
      • bhl 3y ago
        > In finance, for example, there may be situations in currency or options trading where buying and selling in one sequence is more profitable than taking a different path, and these can be modeled using negative weights as long as the search algorithm is fast enough. This is a non-contrived example. You could do this as a mini-project where you scrape various foreign exchange or cryptocurrency data, and try to find some arbitrage opportunities by running these shortest path algorithms.
        • schneems 3y ago
          To try to restate that. Someone owns currency A then buys B which is a cost, but it has a good exchange rate with currency C and C has a good exchange rate with A. So the B-C-A move yields a profit which would be representative as a negative weight. Is that right?
          • bhl 3y ago
            Yes, if trading BCA results in a profit, either BC or CA has negative weight. Negative weight here just means you can sell a currency more than its cost basis, and or buy a currency for cheaper than its cost basis. Though with arbitrage, you typically want to find a cycle like BCAB so you have more of the initial currency you started off with.
    • heavenlyblue 3y ago
      > The issue with negative weighted edges is that a cycle would result in an infinite loop when finding shortest path No it "could" result in an infinite loop. For driving situations negative weights would probably never yield infinite cycles due to negative weight. For that to happen some laws of physics would need to change drastically (i.e. a longer path yielding lower energy usage the longer it gets is nonsensical in any sense that is sensical in the physical world)
      • klyrs 3y ago
        I use regenerative braking as a driving application -- you gain energy by going downhill. A negative cycle would look like an Escher drawing.
    • empath-nirvana 3y ago
      If I understand correctly, if you find such a loop in a graph of currency exchange rates, that would represent an arbitrage opportunity where you can basically make "infinite money" (although typically those loops close quickly if they're exploitable in the real world).
      • bhl 3y ago
        Yep! Executing arbitrage is definitely harder than finding they exist though.
  • jll29 3y ago
    The problem lies in the non-monotonous structure of the sequence of weight when combining positive and negative weights, which is incompatible with Dijkstra's greedy search, which requires monotonous weight sequences in the traversal.
  • klyrs 3y ago
    A prototypical example today is to take battery range into account in navigation. You charge your battery going downhill, corresponding to a negative edge weight. If you're driving from the top of a mountain, through a valley, to the top of a hill, many of the available routes might end up with a negative cost! Preprocessing is certainly possible, but the result is to densify the graph. That densification can turn a sparse graph with O(n) edges into a dense graph with O(n^2) edges. When the goal is to keep pathfinding to a nearly-linear (roughly O(vertices + edges) with log factors) runtime in the presence of negative weight edges, naive preprocessing blows the budget before you even start pathfinding. The article at hand presents long-sought after algorithms which hit the near-linear runtime goal at the cost of a combination of clever preprocessing and a novel divide&conquer approach. So yes, preprocessing, no, not "just" preprocessing.
    • thethirdone 3y ago
      You can preprocess the battery range problem quite efficiently. If is not possible to gain more charge than the gravitational potential between the endpoints for any path. You can change all of the edge weights from battery charge changes into battery charge as compared to a perfectly efficient car. This would make a downhill edge A->B and uphill edge B->A both have approximately the cost of the average between them which should be decidedly non-negative.
      • deleted 3y ago
        [deleted]
      • Retric 3y ago
        The potential energy from going down hill varies based on vehicle load. A pickup truck filled with gravel or an SUV hauling a trailer would be in a very different situation than the same vehicle making the trip empty the next day. Driver behavior, wind, heater use, preconditioning the battery, etc mean this stuff really should be computed in real time by the vehicle in question.
        • thethirdone 3y ago
  • bunabhucan 3y ago
    I'm an uber eats driver picking up a long delivery but notifications comes in for grubhub and Doordash for two short deliveries with pickups and dropoffs along my existing route.
    • zaroth 3y ago
      But if you make all those stops while my food gets cold, I’m definitely going to call support and reduce the tip!
  • rhelz 3y ago
    Its pretty hard to give any problem which you absolutely have to solve using only one particular technique. Nevertheless, there are some problems which require more than just being able to add positive numbers together in order to solve. Consider, for example, the problem of moving an electric car with regenerative braking along a grid of very hilly roads, using minimal charge from the battery. When you go down a hill, sure, you can add energy to your battery by hitting the brakes. But when you go uphill again, you may have to drain your battery of charge. Indeed, if you can find a course which is largely downhill, you may very well end uo with a "negative amount of energy charged" to the battery :-)
    • ozarker 3y ago
      That’s a great example. Thank you
  • deleted 3y ago
    [deleted]
  • thomasahle 3y ago
    What kind of normalization are you thinking of? Like adding a constant to all edge weights?
    • shoo 3y ago
      A sibling comment linking to Johnson's algorithm shows a way to do it. To me, adding a constant to all edges seems like an obvious idea to try-- but one issue is that it will distort the ranking for paths that have different numbers of edges. Ideally a normalisation would preserve the ranking of paths so that a path with minimal unnormalised weight would also be a path of minimal normalised weight. But ranking won't be preserved by adding a constant C to all edge weights, now paths with more edges will be unfairly penalised.
      • pedrosorio 3y ago
        > To me, adding a constant to all edges seems like an obvious idea to try Yeah, as you explained that is not useful because it does not preserve the shortest-path of the original graph (which is the reason we are making all edges non-negative in the first place). That is why Johnson's algorithm adds an edge-dependent weight to each of the edges.
      • thomasahle 3y ago
        Johnson's algorithm appears to run Bellman–Ford as a sub-routine. At that point you are already spending |V||E| time, so you are not getting anywhere close to the performance of Dijkstra and the new algorithm. But I guess you are saying that this preprocessing is OK if you need to run many single-source-shortest-path queries on the graph.
  • riedel 3y ago
    >In finance, for example, there may be situations in currency or options trading where buying and selling in one sequence is more profitable than taking a different path, and these can be modeled using negative weights as long as the search algorithm is fast enough. But those negative weights can throw Dijkstra's shortest-path algorithm for a loop.
    • thaumasiotes 3y ago
      The obvious model of that to me would involve all positive weights representing the exchange ratio, but a path through a graph like that wouldn't be summing the edge weights. I guess the idea is that you weight the edges with the log of the exchange ratio?
  • gnull 3y ago
    > Couldn’t you just preprocess the edges and normalize their weights? How exactly?
    • taneq 3y ago
      Just find the most negative weight and add that to all of the weights? Edit: Oops, as another commenter points out above, this penalizes paths with more steps. I knew it was too easy. :P
      • gnull 3y ago
        Yes, indeed. I think you can prove that one can't just map the edge weights (so that edge's new weight only depends on its original weight) to make all weights positive, and also preserve all shortest paths. You may try something more complex, i.e. where the new weight of an edge would depend on some more edges around it. But then the cost of doing so may be close to Bellman-Ford algorithm itself.
    • nullc 3y ago
      Assuming a directed graph. At the entry to each negative edge collect all the nodes reachable in 1 extra hop from that edge and compute the total cost. All that have a positive weight, add as edges from the source of the negative edge. If they still have a negative weight, expand further. Once you're done, drop all the negative edges. This essentially replaces every negative edge with a set of 'shortcuts' that encode all the places the negative edge could have gotten you, such that the shortcuts have positive cost. Use regular Dijkstra on the augmented graph. This obviously has a potentially exponential complexity, though it will work if there isn't too much negativity. It should at least be enough to convince you that preprocessing is possible absent the existence of negative cost loops.
  • ouid 3y ago
    [dead]
  • sam2426679 3y ago
    > Couldn’t you just preprocess the edges and normalize their weights? In case it’s unclear, the article from OP is effectively doing this: > The team found it was possible to divide the input graph into clusters of low-diameter subgraphs, and then to progressively rework the weights using a series of price functions to build a restructured graph that could be processed almost completely using Dijkstra's algorithm. This involved the random removal of paths with negative weights that would enable the source graph to be converted into a directed acyclic graph: one with only forward paths and no loops connecting the strongly connected clusters to each other. This form was selected because it opened the door to tools that would allow the use of the fastest algorithm. A later phase then reintroduces the missing negative-weight edges. The small number of these paths can be processed using the Bellman-Ford algorithm with comparatively little impact on runtime.
• carterschonwald 3y ago
  https://arxiv.org/abs/2203.03456 https://arxiv.org/abs/2203.03456 And https://arxiv.org/abs/2203.00671 https://arxiv.org/abs/2203.00671 Are the relevant papers
• pradn 3y ago
  This is precisely the sort of article where a bit of notation and interactive graphics would go far in presenting the information. Anyone who can understand this article knows big-O notation. It's silly to assume the article is more accessible just because it's in English.
• cvoss 3y ago
  What is meant by "nodes" in this article? > sum of the number of nodes and connections > Bellman-Ford instead needs many more steps: The total is based on the product of the number of nodes and vertices. > reduced the complexity to the square root of the number of vertices multiplied by the number of nodes At first I thought it was a synonym for vertices, in the same way the article inconsistently uses "connections" for edges. But then "nodes" gets used in the same breath as "vertices" in a way that contradicts that hypothesis.
  • brutusborn 3y ago
    I only had a quick skim but the first paper describes a graph transformation to remove cycles. So I think that nodes are essentially a subgraph of vertices that contain cycles.
  • dataflow 3y ago
    Looks like a significant and confusing typographical error to me. In the 2nd and 3rd item I think by "nodes" they actually meant "edges". The paper in question in the 3rd item you listed is Scaling algorithms for the shortest paths problem, in which the paper says [1] the complexity is proportional to the square root of the number of "nodes", multiplied by the number of "arcs" (edges). [1] https://epubs.siam.org/doi/epdf/10.1137/S0097539792231179 https://epubs.siam.org/doi/epdf/10.1137/S0097539792231179