Shortest path between two vertex

Question

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)?

thanks to all.

Answer 1

First perform a DFS to remove all the vertex that are not accessible from the source.

Then apply the same idea as Dijkstra's algorithm:

dist[source]  := 0                     // Distance from source to source
stack := [source]                      // Stack that we use to remember vertices 
for each vertex v in Graph:        // Initializations
   if v != source
     dist[v]  := infinity           // Unknown distance function from source to v
     previous[v]  := undefined      // Previous node in optimal path from source
   end if 
end for

while stack is not empty:         // The main loop
  u := pop(stack)                   // take the first vertex in the stack

  for each edge (u,v) in E
     alt := dist[u] + length(u, v)
     if alt < dist[v]:               // A shorter path to v has been found
       dist[v]  := alt 
       previous[v]  := u 
     end if
     remove (u,v) from E             // That edge is useless know
     if there is no (u',v) in E      // v is now not reachable
        push(v,stack)                // store v for later
     end if
   end for

end while
return dist[], previous[]

Why it works: when you push a vertex you are sure that you found the shortest distance to it.

Why it is in $O(E+V)$ because each time you use an edge you remove it.

I hope it helps.