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

Тема в разделе "C/C++/C#", создана пользователем nooob, 22 дек 2011.

  1. nooob

    nooob Гость

    Репутация:
    0
    Доброго всем время суток!! В универе задали на РГР написать программу в С, которая находит кратчайший путь между двумя вершинами графа, методом Шимбела. Но я не знаю как это сделать!!! По этому обращаюсь к вам!! Помогите пожалуйста!!!
    Еще, вот нашел принцип метода Шимбела- http://asu.pstu.ru/data/docs-dm/posobie/file2.pdf но как реализовать в С не знаю!!(( Всем заранее спасибо!!
    Так же есть код, но он почему то не работает!!(
    что никто не знает!!!???О_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.
     
  2. Corp

    Corp Гость

    Репутация:
    0
    могу помочь (не за бесплатно)
    ICQ 451099546
     
Загрузка...

Поделиться этой страницей