Vektor se chová zvláštně – C / C++ – Fórum – Programujte.com

Mám takový problém a jsem celkem v koncích. Jsem ochotný zaplatit formou například kreditu na mobilní sítě ČR, neboť můj problém celkem hoří (je to úkol v rámci jendoho projektu).

Jedná se o Floyd-Warshallův algoritmus, jehož základ jsem našel v této podobě (posléze jsem se ho pokusil upravit, nicméně stále neúspěšně, takže pošlu základní tvar).

#include <vector>

#include <iostream>

#include <string>



using namespace std;



typedef vector<int> Column;

typedef vector<Column> Matrix;



void path(int start, int dest, Matrix& paths);



int main(int argc, char* argv[])

{

int n; //number of vertices

cout<<"Please enter the number of vertices: "<<endl;

cin>>n;

cout<<endl;



Matrix wMatrix;

Matrix paths;



// get weight matrix

cout<<"please fill the adjacency matrix, use -1 for absent paths:"<<endl;

int temp=0;

for (int i=1; i<=n; i++)

{

Column column, tempcolumn;

for (int j=1; j<=n; j++)

{

cout<<"W["<<i<<"]["<<j<<"]: ";

           cin>>temp;

if(temp==-1) temp= 65536;

column.push_back(temp);

tempcolumn.push_back(-1);

}

wMatrix.push_back(column);

paths.push_back(tempcolumn);

}





   // floyd algorithm

for (int k=0; k<n; k++)

for (int i=0; i<n; i++)

for (int j=0; j<n; j++)

if (wMatrix[i][k]+wMatrix[k][j] < wMatrix[i][j])

{

paths[i][j] = k;

wMatrix[i][j] = wMatrix[i][k]+wMatrix[k][j];

}



// give shortest path

while(true)

{

int start,dest;

string answer;

cout<<"Please enter the number of start vertex: ";

cin>>start;

cout<<"and destination: ";

cin>>dest;

cout<<endl;

cout<<"Intermediate vertices:";

path(start-1,dest-1,paths);



cout<<endl<<endl<<"Do you want to find another shortest path?(yes or no) ";

cin>>answer;

if( answer != "yes" )

break;

}



return 0;

}



void path(int start, int dest, Matrix& paths)

{

if (paths[start][dest] != -1)

{

path(start, paths[start][dest],paths);

cout<<"->"<<paths[start][dest]+1;

path(paths[start][dest],dest,paths);

}

}

void path(int start, int dest, Matrix& paths)

{

if (paths[start][dest] != -1)

{

path(start, paths[start][dest],paths);

cout<<"->"<<paths[start][dest]+1;

path(paths[start][dest],dest,paths);

}

}

To Vkoncich:

Nestačilo by toto řešení? Odkaz jsem našel na wikipedii.
http://www.ece.rice.edu/~jpr/research/fwarsh.html
Je to sice anglicky, ale není na tom nic k nepohopení. A jelikož jsem líný zjišťovat, jak pracuje tento algoritmus, tak nevím jestli je správně.

S tímto jsem již pracoval a ukázal se být v některých směrech nevyhovující. Každopádně děkuji, ale tohle není to pravé.

To Vkoncich:
No, je pozdě a nutíš mě přemýšlet. Raději uveď,co ti na tomto algoritmu ,který jsi zde uvedl ty, nefunguje? Porovnával jsem ho s http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization a výsleky jsou shodné. Jen ti teda nevypisuje délku cesty, ale v tom nevidím problém...

Mimochodem obrázek,který se nachází nahoře té stránky(ne toho appletu), je špatně - má prohozeny vrcholy 5 a 4, ostatně to je patrné i matice sousednosti(dosažitelosti), která je pod ním(nebo z toho appletu).

a pri čom nevyhovuje ?

ps: Ako som floyda pochopil ja : http://www.ehoy.wz.cz/view.php?cisloclanku=2007010002

Ok, no podívám se na to, každopádně děkuji za rady