Algorithmen Übungen WS 2008/2009

In einer Forschungsarbeit aus dem Jahre 1999 ("The Small World Web") wird gezeigt, dass das World Wide Web die Eigenschaft hat, dass man bei beliebigen, zufällig gewählten Webseiten im Durchschnitt 19 Links folgen muss, um von der einen Webseite auf die andere Webseite zu gelangen. Diese Eigenschaft lässt sich auch bezogen auf einen Graphen interpretieren: Knoten entsprechen Webseiten, Kanten entsprechen Links, und die durchschnittliche Entfernung zwischen je zwei Knoten im Graph entspricht der erwarteten Anzahl an Links, denen man folgen muss um von einer Webseite zu einer anderen Webseite zu gelangen.

In dieser Aufgabe bekommen Sie einen Graphen, für den Sie die durchschnittliche Entfernung zwischen je zwei Knoten bestimmen sollen.

Eingabe

Die erste Zeile der Eingabe enthält eine Zahl n ≤ 200, die Anzahl an Knoten im Graph. Die folgenden n Zeilen enthalten n Zeichen, wobei das j.-te Zeichen in der i.-ten Zeile angibt, ob von Knoten i zu Knoten j eine Verbindung existiert oder nicht. Das Zeichen 'Y' bedeutet, dass die Verbindung existiert, und 'N' bedeutet, dass sie nicht existiert. Sie können annehmen, dass von jedem Knoten zu jedem anderen Knoten ein Pfad existiert.

Ausgabe

Geben Sie die durchschnittliche Länge der kürzesten Wege zwischen je zwei verschiedenen Knoten im Graphen als gekürzten Bruch aus im Format "Zähler/Nenner" (siehe Beispiel).

Beispiel

Eingabe:
4
NYYN
NNNY
YNNN
NNYN

Ausgabe:
11/6

Erklärung zum Beispiel

Die Länge des kürzesten Weges von Knoten 1 zu Knoten 2, 3, und 4 ist 1, 1, bzw. 2. Vom Knoten 2 zu den Knoten 1, 3 und 4 haben die kürzesten Wege die Längen 3, 2, und 1, vom Knoten 3 zu den Knoten 1, 2, und 4 die Längen 1, 2, und 3. Vom Knoten 4 zu den Knoten 1, 2, und 3 haben die kürzesten Wege die Längen 2, 3, und 1. Die Summe dieser Pfadlängen ist 1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22. Da es 12 Paare von Knoten gibt, zwischen denen die kürzesten Wege berechnet werden, ergibt sich eine durchschnittliche Pfadlänge von 22/12, was als gekürzter Bruch 11/6 ergibt.