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

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

  1. nooob

    nooob Гость

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

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

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