C++ Solution UVA 821 - Page Hopping Floyd Warshall Simulation Explanation and stl set

Problem Link:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=762

---

Problem Explanation & Visalization:

Here, the the things to notice are,
1. The graph will be directed. For two node $ a $ and $ b $ an input of $ a \ b $ only implies path from $ a $ to $ b $ and not $ b $ to $ a $.
2. In the graph there will be at least one path from every node to every other node.
3. The input will only have two nodes denoting an edge between them. The graph will be unweighted and directed.

Here, nodes will be numbered from $ 1 $ to $ 100 $ meaning maximum number of nodes will be $ |V_{max}| = 100 $ and for a dense graph there may be an edge from each node to each other node. So $ |V^2| = 10000 $ edges.

I have solved it with floyd warshall algorithm since it is very is to implement. It can also be solved with dijkstra's algorithm, bfs and other applicable algorithms. The task here to find all pair of shortest path and divide by all pair shortest paths count.

---

Understanding the given example:

Input:

1 2   2 4   1 3   3 1   4 3   0 0

Since there are $ N $ nodes and paths to every other node from every node and also no self edges. For each node there are $ (N-1) $ shortest paths to other nodes. So for $ N $ nodes there are $ N(N-1) $ shortest paths in total.

The formula can be written as,

$ Path \ Length_{average} = \frac{\sum_{i=1}^N \text{sum shortest path to all other nodes}}{N(N-1)} $

In the given example there are N = 4 nodes. So there are total of $ N(N-1) = 4(4-1) = 12 $ shortest paths in total.

Simulation:

Note that the code is $ 0 $ indexed and my example is $ 1 $ indexed. No change when taking $ k = 1 $ as intermediate node.

k	i	j	dij	dik + dkj
1	1	1	0	0 + 0
		2	1	0 + 1
		3	1	0 + 1
		4	∞	0 + ∞
	2	1	∞	∞ + 0
		2	0	∞ + 1
		3	∞	∞ + 1
		4	1	∞ + ∞
	3	1	1	1 + 0
		2	∞	1 + 1
		3	0	1 + 1
		4	∞	1 + ∞
	4	1	∞	∞ + 0
		2	∞	∞ + 1
		3	1	∞ + 1
		4	0	∞ + ∞

Now taking $ k = 2 $ as an intermediate node there are improvements. I will only show one example below. Doing full simulation will require a lot of effort. I will stop the simulation when an improvement is found.

k	i	j	dij	dik + dkj
2	1	1	0	1 + ∞
		2	1	1 + 0
		3	1	1 + ∞
		4	∞	1 + 1

Note for $ (i, j, k) = (1, 4, 2) $ here, when taking $ k = 2 $ as an intermediate node for going from node $ 1 $ to node $ 4 $ the distance can be improved from $ ∞ $ to $ 2 $.
Previously the situation was $ 1 \xrightarrow[]{d_{ij} = ∞} 4 $. From node $ 1 $ to $ 4 $ distance was infinite or unreachable. Now taking $ K = 2 $ as an intermediate node the path is improved. Now, $ 1 \xrightarrow[]{d_{ik} = 1} 2 \xrightarrow[]{d_{kj} = 1} 4 $. So now the path from $ i $ to $ j $ or, $ 1 $ to $ 4 $ becomes $ 1 \xrightarrow[]{d_{ij} = 2} 4 $.

Now in the code,

$ graph[i][j] > graph[i][k] + graph[k][j] $
$ graph[1][4] > graph[1][2] + graph[2][4] $

The condition becomes $ INF > 2 $, which is true. So, $ graph[i][j] $ will be replaced by the value of $ graph[i][k] + graph[k][j] $, since a smaller distance is found.

$ graph[i][j] = graph[i][k] + graph[k][j] $
$ graph[1][4] = graph[1][2] + graph[2][4] $
$ graph[1][4] = 2 $

---

Input & Output:

  Input:
 1 2 2 4 1 3 3 1 4 3 0 0
 1 2 1 4 4 2 2 7 7 1 0 0
 0 0

  Output:
 Case 1: average length between pages = 1.833 clicks
 Case 2: average length between pages = 1.750 clicks

---

More input and output in udebug:

https://www.udebug.com/UVa/821

---

Code: