CODEWITHSUNDEEP
pythongraph-theoryshortest-pathdijkstrapath-finding
Karolina Andruszkiewicz
Karolina Andruszkiewicz

Reputation: 509

How does critical path for shortest path problem differ from Dijkstra?

I am trying to find shortest path using critical path on a topologically sorted graph. I found a sample code here and adapted it to find the shortest path instead of the longest one:

        dist[start_node] = (0, start_node)
        while (len(sorted_stack) > 0):

            u = sorted_stack[0]
            del sorted_stack[0]

            for edge in self.get_neighbour_edges(u):
                if (dist[edge.fix_to.name][0] > (dist[edge.fix_from.name][0] + edge.cost)):
                    dist[edge.fix_to.name] = ((dist[edge.fix_from.name][0] + edge.cost), u.name)

        print(self.get_path_from_dist_map(dist, start_node, end_node))

It works, it finds the shortest path very fast, however I wonder if my implementation is indeed the critical path finding and how does it differ from Dijkstra? It seems to be the same thing to me.

Upvotes: 0

Views: 417

Answers (1)

ravenspoint
ravenspoint

Reputation: 20616

Critical path is a project planning concept. Assuming that the edges are tasks, the edge cost is the time taken for a task to complete, and a task cannot begin until the source node of an edge has all the edge tasks leading into the source node complete, then the graph can be interpreted as a project schedule. https://en.wikipedia.org/wiki/Critical_path_method

The Dijkstra algorithm will find the cheapest path through a network, no matter what the interpretation of the nodes, edges and edge costs may be.

However the shortest path is not the critical path.

For example

Start -> A cost 1
A -> B cost 1
B -> end cost 1
Start -> end cost 1

The cheapest path is Start, End

But the critical path is Start, A, B, End and the project cannot be completed before 3 time units

Upvotes: 1

Related Questions