Directed graph (topological sort)

Question

Say there exists a directed graph, G(V, E) (V represents vertices and E represents edges), where each edge (x, y) is associated with a weight (x, y) where the weight is an integer between 1 and 10.

Assume s and tare some vertices in V.

I would like to compute the shortest path from s to t in time O(m + n), where m is the number of vertices and n is the number of edges.

Would I be on the right track in implementing topological sort to accomplish this? Or is there another technique that I am overlooking?

Answer 1

The algorithm you need to use for finding the minimal path from a given vertex to another in a weighted graph is Dijkstra's algorithm. Unfortunately its complexity is O(n*log(n) + m) which may be more than you try to accomplish.

However in your case the edges are special - their weights have only 10 valid values. Thus you can implement a special data structure(kind of a heap, but takes advantage of the small dataset for the wights) to have all operations constant.

One possible way to do that is to have 10 lists - one for each weight. Adding an edge in the data structure is simply append to a list. Finding the minimum element is iteration over the 10 lists to find the first one that is non-empty. This still is constant as no more than 10 iterations will be performed. Removing the minimum element is also pretty straight-forward - simple removal from a list.

Using Dijkstra's algorithm with some data structure of the same asymptotic complexity will be what you need.