1. it is used only when we already know start node to all nodes
this means that source node should be single.
2. It will fail if graph has negative distance. distance or weight should be > 0
3. it is also called single-source shortest path or SSSP algorithm.
1. it is used to find all nodes to all nodes
2. This only fails when there are negative cycles.
4. We can have one or more links of negative cost, c(x, y)<0,
Later on, I will Study Bellman-Ford and also post on blog.
1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3 dist[v][v] ← 0
4 for each edge (u,v)
5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)
6 forkfrom 1 to |V|
7 forifrom 1 to |V|
8 forjfrom 1 to |V|
9 if dist[i][j] > dist[i][k] + dist[k][j]
10 dist[i][j] ← dist[i][k] + dist[k][j]
11 end if
1. line 3, define graph and initialize value. in my case Integer.max
2. line 5, set real weight of edge between two nodes.
3. find dist[i][j] through k node. .. repeatedly k = 1 to last node
find and set if dist[i][j] < dist[i][k] + dist[k][j], in other words, find minimum path and update minimum distance
continue and continue.....
Finally we get shorted graph from all nodes to all node
Last time, I wrote about shortest path by using dijkstra, with above graph.
at that time, test case was 1 to 5 , and result is 20. and also this result by using floyd is the same as using dijkstra.