Поиск Кратчайших Путей Между Двумя Вершинами Графа Методом Шимбела

[nooob]

Доброго всем время суток!! В универе задали на РГР написать программу в С, которая находит кратчайший путь между двумя вершинами графа, методом Шимбела. Но я не знаю как это сделать!!! По этому обращаюсь к вам!! Помогите пожалуйста!!!
Еще, вот нашел принцип метода Шимбела-

Ссылка скрыта от гостей

но как реализовать в С не знаю!!(( Всем заранее спасибо!!
Так же есть код, но он почему то не работает!!(
что никто не знает!!!???О_0

#include <iostream.h>
#include <fstream.h>
#include<conio.h>
main(int argc, char *argv[]) {
//definition of the variables.
int mtx1[20][20], mtx2[20][20], mtx3[20][20], mtx4[20][20];
int n, i, j, k;
int nlink=2, max=9999;

//exit if the number of arguments is not 1.
if(argc != 2) {
cerr << "Usage: shimbel <filename>\n";
return 1;
}

//open the input file. exit if an error occurs.
ifstream fin(argv[1]);
if(!fin) {
cerr << "Can't open file!\n";
return 1;
}

//read the input file.
fin >> n;			//read the number of rows and columns.
for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
fin >> mtx1[i][j];	//read the elements of the matrix.
}
}
fin.close();				//close the file.

for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
mtx2[i][j] = mtx1[i][j];	//copy elements of mtx1 into mtx2.
}
}

for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
mtx4[i][j] = 9999;		//set elements of mtx4 as 9999.
}
}

for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
if(i == j) {
mtx4[i][j] = 0;	//put 0 in the diagonal elements.
} else if(mtx1[i][j] == 1) {
mtx4[i][j] = 1;	//put 1 if a linkage exists between the nodal pair.
}
}
}

nlink = 2;		//start with 2 step path.
while(1) {		//endless loop
for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
mtx3[i][j] = 0;	//set elements of mtx3 as 0.
}
}

for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
for(k=1; k<=n; k++) {
mtx3[i][j] += mtx2[i][k] * mtx1[k][j];	//multiply the matrices.
}
if (mtx3[i][j] != 0){
if(mtx4[i][j] > nlink) {
mtx4[i][j] = nlink;	//put the step number in the nodal pair when it becomes non-zero firstly.
}
}
}
}

//get the maximum element of mtx4.
max = 0;
for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
if(mtx4[i][j] > max) {
max = mtx4[i][j];
}
}
}
if(max < 9999) break;	//if the maximun is not 9999, exit the loop.

for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
mtx2[i][j] = mtx3[i][j];	//copy elements of mtx3 into mtx2.
}
}

nlink++;				//increment nlink.
}							//end of the loop.

//output the results.
cout << n << "\n";			//number of rows and columuns
for(j=1; j<=n; j++) {
for(i=1; i<=n; i++) {
cout << mtx4[i][j];	//elements of the matrix
if(i < n) {
cout << "\t";
}
}
cout << "\n";
}

return 0;
}	//end of the program.

 

[Corp]

могу помочь (не за бесплатно)
ICQ 451099546