Shortest-Path Algorithms

Floyd-Warshall Algorithm

This is not a very efficient algorithm because it runs in $O(n^3)$. However, it is very easy to understand and I actually had to implement one during my first contest (YAC 3).

• Unique Characteristic: Finds all shortest paths in a single run.

Since the implementation is simple, this algorithm might be a good choice. However, the algorithm can only be used when the graph is so small that a $O(n^3)$ time complexity is fast enough.

Code

Implemented using adjacency matrix adj and distance matrix dist.

for (int i = 1; i <= n; i++) { 
	for (int j = 1; j <= n; j++) { 
		if (i == j) dist[i][j] = 0; 
		else if (adj[i][j]) dist[i][j] = adj[i][j]; 
		else dist[i][j] = INF; 
	} 
}

Afterwards, use k as the intermediary to calculate the shortest distances.

for (int k = 1; k <= n; k++) { 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { 
			distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j]); 
		} 
	} 
}