sensei11's blog

Transitive closure and Floyd's algorithm
By sensei11, history, 9 years ago, In English

I was solving https://community.topcoder.com/stat?c=problem_statement&pm=12692&rd=15698.

Editorial : apps.topcoder.com/wiki/display/tc/SRM+586

I could follow the editorial till the section on "Transitivity". I don't understand how using Floyd's algorithm ensures that all constraints are satisified and what exactly is Transitive Closure. I looked up the term in graph theory though I don't see how it applies in this scenario.

Any help regarding the above matter would be appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Do you know about google? wiki

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As I've mentioned I've already looked it up though I don't get how does it apply in case of the given problem

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Then I don't understand what you don't understand. Look at section "Transitivity":
      When there are more than 2 nations, then we should also worry about constraints that can be inferred from the initial ones.

      There is a relationship between three nations based on the pair-wise differences. For three nations i, j and k: Mik is the minimum allowed difference between k and i, Mkj is the minimum allowed difference between j and k. If j and i were too far apart, then it wouldn't be possible to fulfill the conditions Mik and Mkj, so we need the distance between j and i to be at most (Mik+Mkj). This updates the constraint Mij:

      Mij=max(Mij,Mik+Mkj)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Correct me if I'm wrong. From Hikari9's comment and your reply I get the following

        When we update the constraints we look at only three nations. We don't consider more nations, i.e. we don't do something like Mij = max(Mij,Mia+Mab+Mbc+Mcj);

        Application of Floyds algorithm ensures that constraints involving more than 3 countries also hold

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Transitivity means that if u, v are connected and v, w are connected, then u, w are also connected. Floyd's transitive closure is an O(n^3) algorithm that transforms an adjacency matrix into a connection matrix. Meaning, all transitivites are already "closed" with adj[u][v] true if they are connected rather than merely just sharing an edge.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read the problem statement yet but I can explain what a transitive closure is.

Given the graph G(V, E), the transitive closure Gt of G is a graph Gt(V, Et) where there is an edge iff there is a path from u to v in G.

→ Reply