 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
zengrz
Cheater
![]() Reputation: 0
Joined: 19 Mar 2009
Posts: 33
Location: ca
|
 Posted: Mon Jan 04, 2010 4:59 am Post subject: Need help - Floyd-Warshall's algorithm |
 |
|
Sorry need some help again.
Here's what i understand so far (idk right or wrong):
- works in an adjacency matrix
- finds all shortest paths between all pairs of vertices
- works for graphs with negative edges as well
Algorithm:
shorestpath(i,j,k) find the shortest paths between i to j using nodes 1 through k.
at the heart of the algorithm lies this
shortestPath(i,j,k) = min{shortestPath(i,j,k − 1),shortestPath(i,k,k − 1) + shortestPath(k,j,k − 1)}
which translates to
the shortest path between i and j through nodes 1 to k =
minimum of shortestPath(i,j,k − 1) and shortestPath(i,k,k − 1) + shortestPath(k,j,k − 1)
if there exist some node k that allows traveling from i to j fast by using k instead of 1 to k-1?
what is the base case of this recursion? help thanks a lot! illustration will be great. pls correct anything if i m wrong
btw, does the adjacency matrix gets updated at the end of the operation?
it seems that a new matrix is being created and updated as the algorithm is running, is it necessary?
thanks a ton!
|
|
| Back to top |
|
 |
Flyte
Peanuts!!!!
 Reputation: 6
Joined: 19 Apr 2006
Posts: 1887
Location: Canada
|
| Posted: Mon Jan 04, 2010 1:32 pm Post subject: |
|
|
Iff shortestPath(i, j, 0) then you return the cost of i -> j.
I've got to go to class, I'll provide an example in a few hours if you need one.
|
|
| Back to top |
|
|
zengrz
Cheater
![]() Reputation: 0
Joined: 19 Mar 2009
Posts: 33
Location: ca
|
| Posted: Mon Jan 04, 2010 6:14 pm Post subject: |
|
|
| Flyte wrote: | If shortestPath(i, j, 0) then you return the cost of i -> j.
|
is 0 one of the nodes in 1 to k-1?
example will be great thx a lot!
|
|
| Back to top |
|
|
Flyte
Peanuts!!!!
Reputation: 6
Joined: 19 Apr 2006
Posts: 1887
Location: Canada
|
| Posted: Mon Jan 04, 2010 6:36 pm Post subject: |
|
|
For the weighted matrix of:
| Code: | A--1--B
|\ |
| \ |
5 3 1
| \ |
| \|
C--1--D |
| Code: | #include <iostream>
#include <iomanip>
#include <sstream>
using namespace std;
// This is for printing. Nothing to do with the formula.
template <unsigned int N>
string FormatMatrix(unsigned int (& matrix)[N][N]) {
stringstream ss;
for(unsigned int i = 0; i < N; ++i) {
ss << "| ";
for(unsigned int j = 0; j < N; ++j) {
ss << setw(2) << matrix[i][j] << " ";
}
ss << "|" << endl;
}
return ss.str();
}
// N for our matrix is 4
template <unsigned int N>
void FloydWarshall(unsigned int (& matrix)[N][N]) {
for(unsigned int k = 0; k < N; ++k) {
for(unsigned int i = 0; i < N; ++i) {
for(unsigned int j = 0; j < N; ++j) {
if(matrix[i][k] * matrix[k][j] != 0 && i != j) {
const unsigned int dist = matrix[i][k] + matrix[k][j];
if(dist < matrix[i][j] || !matrix[i][j]) {
matrix[i][j] = dist;
}
}
}
}
}
}
// Our matrix
unsigned int weightedAdjacencyMatrix[4][4] = {
{ 0, 1, 5, 3 },
{ 1, 0, 0, 1 },
{ 5, 0, 0, 1 },
{ 3, 1, 1, 0 }
};
int main()
{
cout << "Before: " << endl << FormatMatrix(weightedAdjacencyMatrix) << endl;
FloydWarshall(weightedAdjacencyMatrix);
cout << "After: " << endl << FormatMatrix(weightedAdjacencyMatrix) << endl;
for(int i = 0; i < 4; i++) {
cout << "A -> " << (char)('A'+i) << ": " << weightedAdjacencyMatrix[0][i] << endl;
}
return 0;
} |
Output is:
| Code: | Before:
| 0 1 5 3 |
| 1 0 0 1 |
| 5 0 0 1 |
| 3 1 1 0 |
After:
| 0 1 3 2 |
| 1 0 2 1 |
| 3 2 0 1 |
| 2 1 1 0 |
A -> A: 0
A -> B: 1
A -> C: 3
A -> D: 2 |
|
|
| Back to top |
|
|
zengrz
Cheater
![]() Reputation: 0
Joined: 19 Mar 2009
Posts: 33
Location: ca
|
| Posted: Mon Jan 04, 2010 7:46 pm Post subject: |
|
|
that looks perfect, really appreciate the help!
btw does it matter if i switch the order of the loops? i tried to invert the order (for j..i..k) and the dist from A -> C becomes 4 instead of 3 while others stay the same. is it illegal to switch?
thx for the great help again!
|
|
| Back to top |
|
|
Flyte
Peanuts!!!!
Reputation: 6
Joined: 19 Apr 2006
Posts: 1887
Location: Canada
|
| Posted: Mon Jan 04, 2010 7:56 pm Post subject: |
|
|
| zengrz wrote: | that looks perfect, really appreciate the help!
btw does it matter if i switch the order of the loops? i tried to invert the order (for j..i..k) and the dist from A -> C becomes 4 instead of 3 while others stay the same. is it illegal to switch?
thx for the great help again! |
The order matters as it is a dynamic function, i.e. the problem can be broken up into simpler subproblems and the order of these subproblems affect the behavior of the function.
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
