Question

You are given a directed graph in which each node$\mathbf{u}\mathbf{\in }\mathbf{V}\mathbf{,}$ has an associated price${\mathbf{p}}_{\mathbf{u}}$ which is a positive integer. Define the array cost as follows: for each $\mathbf{u}\mathbf{\in }\mathbf{V}\mathbf{,}$

$\mathbf{cost}\mathbf{\left[}\mathbf{u}\mathbf{\right]}$ = price of the cheapest node reachable from$\mathbf{u}$ (including$\mathbf{u}$ itself).

For instance, in the graph below (with prices shown for each vertex), the cost values of the nodes $\mathbf{A}\mathbf{,}\mathbf{B}\mathbf{,}\mathbf{C}\mathbf{,}\mathbf{D}\mathbf{,}\mathbf{E}\mathbf{,}\mathbf{F}\mathbf{}\mathbf{are}\mathbf{}\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{5}\mathbf{,}$respectively.

Your goal is to design an algorithm that fills in the entire cost array (i.e., for all vertices).

(a) Give a linear-time algorithm that works for directed acyclic graphs.

(b) Extend this to a linear-time algorithm that works for all directed graphs.

Short answer

1. The linear time algorithm that works for directed acyclic graphs is given below.
2. Extension of this to a linear-time algorithm that works for all directed graphs is shown below.

Step-by-step solution

Step 1: Directed acyclic graph.

DAG (directed acyclic graph) is a graph which contain directed edges between all the vertices and they are not contain any cycle in graph. This type of graph are called directed acyclic graph.

Step 2: Linear-time algorithm that works for directed acyclic graphs.

a)

Consider the vertices of the DAG in topological order. Let a liberalized order. Vertices reachable from any vertex will be among the vertices (smaller post number) in the linear zed order. Once we have updated costs for vertices. Cost of vertices will be minimum of cost of vertices connected to (including itself). This is because any path from vertex will be through its adjacent vertices of costs for which are already calculated. We implement an algorithm which linearisation the DAG and calculates cost in reverse topological order.

Thealgorithm that works for directed acyclic graphs in Linear-time is shown as:

Pseudo code:

$\begin{array}{l}\begin{array}{l}\mathrm{cost}\left(\mathrm{G}\right)\\ \end{array}\\ \begin{array}{l}\mathrm{DFS}(\mathrm{G},\mathrm{u})//\mathrm{where}\mathrm{u}\mathrm{is}\mathrm{a}\mathrm{randomly}\mathrm{picked}\mathrm{vertex}.\\ \end{array}\\ (\mathrm{v}1,\mathrm{v}2,\\ :::\\ ,\mathrm{vn})\end{array}$

$\begin{array}{l}\mathrm{decreasing}\mathrm{order}\mathrm{of}\mathrm{post}\left[\mathrm{vi}\right]\\ \begin{array}{l}\\ \mathrm{For}\mathrm{i}=\mathrm{n}\mathrm{to}1:\end{array}\\ \begin{array}{l}\\ \mathrm{cost}\left[\mathrm{vi}\right]=\mathrm{price}\left(\mathrm{vi}\right)\end{array}\\ \begin{array}{l}\\ \mathrm{for}\mathrm{all}(\mathrm{vi},\mathrm{vj})\end{array}\end{array}$

The time for linearizing a DAG is linear. And for finding the minimum cost, we visit each edge at most once and hence the time is linear.

Extension to a linear-time algorithm.

b).

For a general directed graph, the cost of any two nodes in the same strongly

connected component will be same since both are reachable from each other. Hence, it is sufficient to run the above algorithm on the DAG of the strongly connected components of the graph. For a node corresponding to strongly connected component, we take price,$\mathrm{C}=\min \left(\mathrm{priceu}\right)$ for all.

Once we have found SCCs, meta-nodes can be topologically sorted by arranging them in decreasing order of their highest post numbers.

Pseudo code:

$\begin{array}{l}\begin{array}{l}\begin{array}{l}\mathrm{procedure}\mathrm{cheapest}\\ \end{array}\\ \begin{array}{l}\mathrm{cost}\left(\mathrm{G}\right)\\ \end{array}\\ \mathrm{DFS}(\mathrm{GR};\mathrm{u})//\mathrm{where}\mathrm{u}\mathrm{is}\mathrm{a}\mathrm{randomly}\mathrm{picked}\mathrm{vertex}\end{array}\\ \mathrm{Run}\mathrm{undirected}\mathrm{connected}\mathrm{components}\mathrm{algorithmon}\mathrm{G}\mathrm{processing}\end{array}$

$\begin{array}{l}\mathrm{vertices}\mathrm{in}\mathrm{decreasing}\mathrm{order}\mathrm{of}\mathrm{postnumbers}\\ \begin{array}{l}\\ \mathrm{post}\left[\mathrm{C}\right]=\max \left(\mathrm{post}\left(\mathrm{u}\right)\right)\mathrm{for}\mathrm{all}\mathrm{u}\mathrm{in}\mathrm{C}\end{array}\\ \begin{array}{l}\\ \mathrm{For}\mathrm{all}\mathrm{c}\mathrm{in}\mathrm{C}(\mathrm{where}\mathrm{C}\mathrm{is}\mathrm{these}\mathrm{to}\mathrm{fall}\mathrm{SCC}\text{'}\mathrm{s}):\end{array}\\ \begin{array}{l}\\ \mathrm{price}\left[\mathrm{c}\right]=\min \left(\mathrm{price}\left(\mathrm{u}\right)\right)\mathrm{for}\mathrm{all}\mathrm{u}\mathrm{in}\mathrm{c}\end{array}\end{array}$

$\begin{array}{l}(\mathrm{c}1,\mathrm{c}2,\\ :::\\ ,\mathrm{cn})\\ \begin{array}{l}\\ \mathrm{decreasing}\mathrm{order}\mathrm{of}\mathrm{post}\left(\mathrm{ci}\right)\end{array}\end{array}$

$\begin{array}{l}\begin{array}{l}\mathrm{For}\mathrm{i}=\mathrm{n}\mathrm{to}1:\\ \end{array}\\ \begin{array}{l}\mathrm{cost}\left[\mathrm{ci}\right]=\mathrm{price}\left[\mathrm{ci}\right]\\ \end{array}\\ \begin{array}{l}\mathrm{for}\mathrm{all}(\mathrm{ci},\mathrm{cj})\\ \end{array}\\ \mathrm{if}\mathrm{cost}\left[\mathrm{cj}\right]<\mathrm{cost}\left[\mathrm{ci}\right]\end{array}$

$\mathrm{cost}\left[\mathrm{ci}\right]=\mathrm{cost}\left[\mathrm{cj}\right]$