MHB Find the greatest of the shortest paths

[evinda]

Hello! (Wave)We define as diameter the greatest of the shortest paths of a graph.

We are given a graph $G=(V,E)$.

I want to write an algorithm that finds the diameter of the graph $G$.

I have tried the following:

    Diam(G) 
    // Let W be a  nxn array with the weight edges of G
    1. FLOYD-WARSHALL(W)
    2. max=d_{11}
    3. for i=1 to n 
    4.     for j=1 to n 
    5.         if (d_(ij)>max) 
    6.             max=d_(ij) 
    7. return max
    
    
    
    FLOYD-WARSHALL(W)
    1.   n=W.rows
    2.   D^(0)=W
    3.   for k=1 to n
    4.       let D^(k)=(d_(ij)^(k)) be a new  nxn matrix
    5.       for i=1 to n
    6.           for j=1 to n
    7.               d_(ij)^(k)=min(d_(ij)^((k-1)), d_(ik)^((k-1))+d_(kj)^(k-1))
    8. return D^(n)

Could you tell me if my idea is right? (Thinking)

 

[caffeinemachine]

Hello! (Wave)We define as diameter the greatest of the shortest paths of a graph.

We are given a graph $G=(V,E)$.

I want to write an algorithm that finds the diameter of the graph $G$.

I have tried the following:

    Diam(G) 
    // Let W be a  nxn array with the weight edges of G
    1. FLOYD-WARSHALL(W)
    2. max=d_{11}
    3. for i=1 to n 
    4.     for j=1 to n 
    5.         if (d_(ij)>max) 
    6.             max=d_(ij) 
    7. return max
    
    
    
    FLOYD-WARSHALL(W)
    1.   n=W.rows
    2.   D^(0)=W
    3.   for k=1 to n
    4.       let D^(k)=(d_(ij)^(k)) be a new  nxn matrix
    5.       for i=1 to n
    6.           for j=1 to n
    7.               d_(ij)^(k)=min(d_(ij)^((k-1)), d_(ik)^((k-1))+d_(kj)^(k-1))
    8. return D^(n)

Could you tell me if my idea is right? (Thinking)

Hello evinda.

I apologize in advance that my post is not helpful in answering your question.

I just want to suggest that if you want your algorithm checked then you should actually put your algorithm rather than the code. Checking someones code is an arduous task.

 

[Evgeny.Makarov]

I have an opinion about your code, but could you explain why you think it computes the graph diameter (without explaining the details of the Floyd–Warshall algorithm)?

 

[evinda]

I have an opinion about your code, but could you explain why you think it computes the graph diameter (without explaining the details of the Floyd–Warshall algorithm)?

The Floyd-Warshall algorithm returns the matrix $D^{(n)}=(d_{ij}^{(n)})$ of shortest-path weights.
Isn't the diameter the maximum of the shortest-path weights?
Or am I wrong?

 

[Evgeny.Makarov]

You are right. But I agree with caffeinemachine that a word description like this is easier to understand then a code.

 

[evinda]

You are right. But I agree with caffeinemachine that a word description like this is easier to understand then a code.

Nice! (Happy)

The time complexity of the algorithm [m]Diam(G)[/m] is $\Theta(n^3)$, since:

• the line 1, where we call FLOYD-WARSHALL(W), requires $\Theta(n^3)$ time,
• the line 2 requires $O(1)$ time,
• the lines 3-6 require $O(n^2)$ time, since each for-loop requires $O(n)$ time and the lines $5,6$ require constant time and finally,
• the line 7 requires contant time.

Does this suffice or do I have to show also that the Floyd-Warshall algorithm requires $O(n^3)$ time?

    Diam(G) 
    // Let W be a  nxn array with the weight edges of G
    1. FLOYD-WARSHALL(W)
    2. max=d_{11}
    3. for i=1 to n 
    4.     for j=1 to n 
    5.         if (d_(ij)>max) 
    6.             max=d_(ij) 
    7. return max
    
    
    
    FLOYD-WARSHALL(W)
    1.   n=W.rows
    2.   D^(0)=W
    3.   for k=1 to n
    4.       let D^(k)=(d_(ij)^(k)) be a new  nxn matrix
    5.       for i=1 to n
    6.           for j=1 to n
    7.               d_(ij)^(k)=min(d_(ij)^((k-1)), d_(ik)^((k-1))+d_(kj)^(k-1))
    8. return D^(n)

 

[Evgeny.Makarov]

the lines 3-6 require $O(n^2)$ time, since each for-loop requires $O(n)$ time and the lines $5,6$ require constant time

I wouldn't say that the outer loop requires $O(n)$ time. When I am talking about a loop, I include its body, and by saying that a loop takes a certain time I mean that it takes that time for the whole loop to finish. So the outer loop takes time $O(n^2)$ because its body (the inner loop) executes $n$ times and each execution takes time $O(n)$.

Does this suffice or do I have to show also that the Floyd-Warshall algorithm requires $O(n^3)$ time?

This is a well-known fact, but it depends on the requirements of your course.

 

[evinda]

I wouldn't say that the outer loop requires $O(n)$ time. When I am talking about a loop, I include its body, and by saying that a loop takes a certain time I mean that it takes that time for the whole loop to finish. So the outer loop takes time $O(n^2)$ because its body (the inner loop) executes $n$ times and each execution takes time $O(n)$.

This is a well-known fact, but it depends on the requirements of your course.

I see... Thanks a lot! (Nod)