I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest path between vertices, but it has to start only in those vertices, which has no input edge going to this vertex (the vertices with red color).
So Dijkstra would be runned only from red vertices. If we run Dijkstra on all vertices, we could assume that complexity is |V|*Dijkstra but in this case we do not need such big complexity. As is one Dijkstra big, another Dijkstra from another vertex would be runned on less vertices.
The more Dijkstras we run, the less vertices could be visited.
Dijkstra from all vertices should have |V|(|E|+|V|*log|V|) complexity. This complexity should be much lower but I can't figure out where to compute.
