| Line 9: | Line 9: | ||
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);<br> | graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);<br> | ||
--[[User:Asuleime|Asuleime]] 09:40, 12 December 2008 (UTC) | --[[User:Asuleime|Asuleime]] 09:40, 12 December 2008 (UTC) | ||
| + | ------ | ||
| + | Why use floyd warshall when we have no negative weights?... | ||
Latest revision as of 15:19, 14 December 2008
My solution (using Dijkstra's algorithm): Length is 16. (path is a to b to e to h to l to m to p to s to z) Does anyone agree/disagree? -Brian (Thomas34 22:16, 10 December 2008 (UTC))
Got the same thing. By the way, the simplest (to implement) way to check the length of the shortest path is by running Floyd-Warshall algorithm on your computer (n is the number of vertices, graph[i][j] - the length of the shortest path between vertices i and j):
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
--Asuleime 09:40, 12 December 2008 (UTC)
Why use floyd warshall when we have no negative weights?...
