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.
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.