CODEWITHSUNDEEP
optimizationgraphdijkstrashortest-pathvertex
Ehsan Khodarahmi
Ehsan Khodarahmi

Reputation: 4922

Optimized recalculating all pairs shortest path when removing vertexes dynamically from an undirected graph

I use following dijkstra implementation to calculate all pairs shortest paths in an undirected graph. After calling calculateAllPaths(), dist[i][j] contains shortest path length between i and j (or Integer.MAX_VALUE if no such path available).
The problem is that some vertexes of my graph are removing dynamically and I should recalculate all paths from scratch to update dist matrix. I'm seeking for a solution to optimize update speed by avoiding unnecessary calculations when a vertex removes from my graph. I already search for solution and I now there is some algorithms such as LPA* to do this, but they seem very complicated and I guess a simpler solution may solve my problem.

public static void calculateAllPaths()
{
    for(int j=graph.length/2+graph.length%2;j>=0;j--)
    {
        calculateAllPathsFromSource(j);
    }
}

public static void calculateAllPathsFromSource(int s)
{
    final boolean visited[] = new boolean[graph.length];

    for (int i=0; i<dist.length; i++)
    {
        if(i == s)
        {
            continue;
        }
        //visit next node
        int next = -1;
        int minDist = Integer.MAX_VALUE;
        for (int j=0; j<dist[s].length; j++)
        {
            if (!visited[j] && dist[s][j] < minDist)
            {
                next = j;
                minDist = dist[s][j];
            }
        }
        if(next == -1)
        {
            continue;
        }
        visited[next] = true;

        for(int v=0;v<graph.length;v++)
        {
            if(v == next || graph[next][v] == -1)
            {
                continue;
            }
            int md = dist[s][next] + graph[next][v];
            if(md < dist[s][v])
            {
                dist[s][v] = dist[v][s] = md;
            }
        }
    }
}

Upvotes: 0

Views: 327

Answers (1)

dfrib
dfrib

Reputation: 73196

If you know that vertices are only being removed dynamically, then instead of just storing the best path matrix dist[i][j], you could also store the permutation of each such path. Say, instead of dist[i][j] you make a custom class myBestPathInfo, and the array of an instance of this, say myBestPathInfo[i][j], contain members best distance as well as permutation of the best path. Preferably, the best path permutation is described as an ordered set of some vertex objects, where the latter are of reference type and unique for each vertex (however used in several myBestPathInfo instances). Such objects could include a boolean property isActive (true/false).

Whenever a vertex is removed, you traverse through the best path permutations for each vertex-vertex pair, to make sure no vertex has been deactivated. Finally, only for broken paths (deactivated vertices) do you re-run Dijkstra's algorithm.

Another solution would be to solve the shortest path for all pairs using linear programming (LP) techniques. A removed vertex can be easily implemented as an additional constraint in your program (e.g. flow in <=0 and and flow out of vertex <= 0*), after which the re-solving of the shortest path LP:s can use the previous optimal solution as a feasible basic feasible solution (BFS) in the dual LPs. This property holds since adding a constraint in the primal LP is equivalent to an additional variable in the dual; hence, previously optimal primal BFS will be feasible in dual after additional constraints. (on-the-fly starting on simplex solver for LPs).

Upvotes: 1

Related Questions