Shortest Path

Question

First Statement is true. 

But I don't know about second?

Comments

Thanks. I got it.

---

1> false. As we have counter case of Selection sort which takes n comparisions at the end of execution.

2> Consider the below algorithm:-

MODIFIED_BFS(G, S)
{
1.    for every v BELONGS G.V
      { 
2.        v.d = INF
3.        V.par = NIL
          v.flag = false
      }
4.    Q = S
5.    while(Q != PHI)
      {
6.        u = Dequeue(Q)
7.        for every v BELONGS u.Adj[u]
          {
8.            if(v.flag == false)
            {
9.                Q = v
            }
10.            if(v.d > u.d + w(u,v))
            {
11.               v.d = u.d + w(u,V)
12.               v.par = U
13.               v.flag = true
            }
        }
    }
}

Line 5 will take O(V) time, and Adj[u] and w(u,v) takes O(E) in total.

Finally TC = O(E) as for dense graph E = V².

---

@Shubhanshu. Thanks

For first statement actually I was considering swaps as comparisons. Yes for selection sort we need atmost O(n) swaps.