2

I'm solving a programming problem involving finding the shortest path between a vertex and the rest of the graph. Currently, I'm using Dijkstra's algorithm to achieve that.

However, the problem involves calling Dijkstra's multiple times with only slight modification each time (changing an edge's weight) and write the output after that.

I'm concerned about doing this with the plain algorithm itself. The graph could get really large and so do the number of modifications need to be made.

I have no idea what I could do. I've thought of Python's cache decorator but I'm using C++ (only C++ or Pascal was allowed) and I'm not sure if cache even help with this.

This is a paper assignment. There're no online judge or large sample inputs and the constraint isn't really clear about the maximum number of vertices, edges, modifications nor the memory and time limit. However, it's likely that the memory limit will be 1GB and time limit will be 1s.

Improve this question
4
  • Shouldn't you be using an A* variant? Or something similar thats allows you to add biases to edge weights to "steer" the search direction. In any case this is a well researched part of graph theory so you are bound to find existing papers on this problem. (Not directly related but nice to see visualizing the A* algorithm` Commented Jan 6, 2024 at 15:18
  • Is it known at the time when the program is running which parts might change and which parts might not change? Commented Jan 6, 2024 at 15:20
  • @LajosArpad No, unfortunately. After the edge inputs will be the modification part. We're supposed to read the modification as {edge_index, new_weight} pair (i.e for {3, 4}, edge #3 connects vertex 3 with 5 for example, will have its weight changed to 4). Commented Jan 6, 2024 at 15:50
  • @PepijnKramer Thank you. I'll see if A* can solve my problem. I'm pretty new into graph theory and this problem is much more a challenge than a requirement. I just want to try solving it anyways. Commented Jan 6, 2024 at 15:52

1 Answer 1

Reset to default
0

When you run Dijkstra's the first time, you store the distance from the source for each vertex.

If you then reduce the weight of an edge from u->v, then you only need to update the distances if the new weight is less than the dist(v)-dist(u).

If you do need to update distances, then you can either run Dijkstra's again, or you can us a modified version starting at v, that only considers vertexes with distances that are reduced.

If you increase an edge weight, then you can run Dijkstra's again only if the edge is in the shortest path tree. Dijkstra's algorithm is easily modified to track that information as well.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

If the weight changes in a bridge, distances should be updated even if the new weight is larger
Oh, I was assuming that all the updates make weights smaller. If an update increases a weight, and that edge is in a shortest path, then I would rerun the whole Dijkstra's

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.