CODEWITHSUNDEEP
algorithmgraphgraph-theory
user4952610
user4952610

Reputation:

Intuition behind the algorithm to compute single source shortest path for every vertex in DAG

The algorithm is as follows:

The algorithm starts by topologically sorting the dag (see Section 22.4) to impose a linear ordering on the vertices. If the dag contains a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.

Can somebody tell me the intuition behind it? And using that intuition please tell how do we find longest path just be negating the edge weights and running the algorithm

We cannot use Dijkstra's algorithm as edges are allowed to have negative weights.

Upvotes: 5

Views: 2443

Answers (3)

Manish
Manish

Reputation: 1

Topological sort ensures that we are picking up nodes that come first while travelling from the source, this, in turn, will ensure that every node will have at least one condition that it can be reached from the source.

for (int i = 0; i < N; i++)
    if (visited[i] == false)
        topologicalSortUtil(i, visited, stack, adj);

for (int i = 0; i < N; i++)
    dist[i] = Integer.MAX_VALUE;
dist[s] = 0;

while (stack.empty() == false)
{
    int node = (int)stack.pop();

    if (dist[node] != Integer.MAX_VALUE)
    {
        enter code here  for(Pair it: adj.get(node)) {
            if(dist[node] + it.getWeight() < dist[it.getV()]) {
                dist[it.getV()] = dist[node] + it.getWeight(); 
            }
        }
    }
}

As we are setting dist[src] = 0, it will start from there, the condition dis[node] != infinity will not let any other node than src enter that condition first. Because of topological sort notes coming before src will be discarded.

Upvotes: 0

Didgeridoo
Didgeridoo

Reputation: 1262

Your question is related to single-source shortest-path problem (SSSP) in DAG. Topological sorting of a graph represents a linear ordering of the graph. It is allowed to process all vertices in topological order (from left to right), and all shortest paths will be found using relaxation property. Running time of the algorithm is O(|V| + |E|), where V is a set of vertices, E is a set of edges.

If you want to find the longest path (or the critical path) there are the next variants:

First way is to negate the edge weights. The path with the smallest negative value will give the longest path (but for algorithm it will still the smallest path). We can do it because topological sorting may work with negative edge weights.

Second way is to change the relaxation step: 

1. Cost of each vertex is initialized to negative infinity
2. Change the relaxation step:
  if d(v) < d(u) + w
  then d(v) = d(u) + w
  else d(v) is remains unchanged

where d - the distance;
u, v - vertices;
w - weight on edge (u, v).

In general case for solving SSSP problem there are Dijkstra's and Bellman-Ford algorithm. The main difference consists in the fact that Bellman-Ford algorithm computes SSSP for any weights in the graph and can detect negative weight cycles in the graph, but Dijkstra's algorithm can work with positive weights.

For more details see Shortest Paths.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59144

Finding the shortest path to a vertex is easy if you already know the shortest paths to all the vertices that can precede it. Finding the longest path to a vertex in DAG is easy if you already know the longest path to all the vertices that can precede it.

Processing the vertices in topological order ensures that by the time you get to a vertex, you've already processed all the vertices that can precede it.

Dijkstra's algorithm is necessary for graphs that can contain cycles, because they can't be topologically sorted.

Upvotes: 15

Related Questions