Chapter 24, Problem 1P

(a)

Program Plan Intro

To represent the graph’s acyclic topological nature.

Explanation of Solution

Given Information: A graph $G=(V,E)$ that is having an arbitrary linear order of vertices $v_1,v_2\mathrm{....},v_{\left|V\right|}$ and edges set partitioned into $E_f\cup E_b$ . Where $E_f=\{(v_i,v_j)\in E:i<j\}$ and $E_b=\{(v_i,v_j)\in E:i>j\}$ . This graph contains no self-loop therefore every edges is in either $E_f$ or $E_b$ .

Explanation:

As mentioned, graph does not contained any self-loop therefore; every edge in graph $G_f$ will go from higher index vertices to lower indexes vertices. It means, it will never come back to same index where it was started and $vice-versa$ .

It means $G_f$ is acyclic and its vertices $(v_1,v_2,\mathrm{.......},v_{\left|V\right|})$ are sorted with topologically. As in same case, vertices $(v_{\left|V\right|},\mathrm{.......},v_2,v_1)$ for graph $G_b$ are sorted topologically.

(b)

Program Plan Intro

To represent the Yen’s improvement in Bellman-Ford algorithm.

Explanation of Solution

Given Information: Implementation of Bellman- Ford algorithm and a graph with relaxing edges of $E_f$ and $E_b$ .

Explanation:

Bellman- Ford algorithm is simpler than Dijkstra’s algorithm and worked very well with distributed systems. In the first step, it calculate the shortest path that is having at-most one edge in bottom-up approach then it will go for at most 2-edges and so-on up to $i^{th}$ iterations. This process proved that there is no negative weight cycle.

In Bellman- Ford algorithm and previous part a declare that the graph’s edges $E_f$ are going in increasing order and $E_b$ are going in decreasing order. It means any sequence $\left\{k_i\right\}i$ of vertices’ length can change from $\left|V\right|$ $to$ $\left|\right|V|/2|$ times and it initially expected that vertices will increase their indexes before it run through $E_f$ and $E_b$ . For this change, vertices will increase $|v+1|$ with respect to represent the sources in ordering of the vertices $\left|v_{k_2}\right|$ .

(c)

Program Plan Intro

To calculate the effects of running time complexity for Bellman-Ford algorithm.

Explanation of Solution

Given Information: Implementation of Bellman- Ford algorithm and a scheme for evaluating the time complexity.

Explanation:

It cannot improve the asymptotic running time of Bellman-Ford algorithm becausehaving a co-efficient of $1$ to $\frac{1}{2}$ .It will drop the runtime of the algorithm.

The final runtime for the algorithm will be ${\rm O}(EV)$ .