(Brian Thomas rhea hw14) |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
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? | 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 ([[User:Thomas34|Thomas34]] 22:16, 10 December 2008 (UTC)) | -Brian ([[User:Thomas34|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):<br> | ||
| + | for(int k=0;k<n;++k)<br> | ||
| + | for(int i=0;i<n;++i)<br> | ||
| + | for(int j=0;j<n;++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) | ||
| + | ------ | ||
| + | Why use floyd warshall when we have no negative weights?... | ||
Latest revision as of 16: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?...
