диаметр графа

Тема в разделе "MS Visual C++", создана пользователем -, 4 дек 2007.

  1. Гость

    Переделывала алгоритм Дейкстры для писка мин путей в поиск максимальных(это и будет радиус)..но что-то работает неправильно.может кто-нибудь знает какой-нибудь другой алгоритм поиска диаметра графа с помощью матрицы смежности?
     
  2. European

    Регистрация:
    4 сен 2006
    Сообщения:
    2.580
    Симпатии:
    0
    Для: Лека
    Если работает не правильно, то может проще найти ошибку, чем искать новый алгоритм
     
  3. Гость

    вот собственно код.может кто-то свежим взглядом заметит ошибку)).комменты остались с поиска кратчайших путей
    #include <stdio.h>
    //#include <iostream.h>
    #include <conio.h>
    #define VERTEXES 6 //Число вершин в графе

    int v;
    int main(int argc, char* argv[])
    {
    // clrscr();
    int infinity=1000;
    int p= VERTEXES;
    int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,
    1,0,5,0,0,1,
    0,5,0,5,20,1,
    0,0,5,0,3,2,
    1,0,20,3,0,10,
    3,1,1,2,10,0 };

    // Будем искать путь из вершины s в вершину g
    int s; // Номер исходной вершины
    int g; // Номер конечной вершины
    printf("Enter s: "); // Номер может изменяться от 0 до p-1
    scanf("%i",&s);
    printf("Enter g: ");
    scanf("%i",&g);
    int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
    // x=0 - еще не найден кратчайший путь в i-ю вершину,
    // x=1 - кратчайший путь в i-ю вершину уже найден
    int t[VERTEXES]; //t - длина кратчайшего пути от вершины s в i
    int h[VERTEXES]; //h - вершина, предшествующая i-й вершине
    // на кратчайшем пути

    // Инициализируем начальные значения массивов
    int u; // Счетчик вершин
    for (u=0;u<p;u++)
    {
    t=infinity; //Сначала все кратчайшие пути из s в i
    //равны бесконечности
    x=0; // и нет кратчайшего пути ни для одной вершины
    }
    h=0; // s - начало пути, поэтому этой вершине ничего не предшествует
    t=0; // Кратчайший путь из s в s равен 0
    x=1; // Для вершины s найден кратчайший путь
    v=s; // Делаем s текущей вершиной

    while(1)
    {
    // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
    for(u=0;u<p;u++)
    {
    if(a[v]==0)continue; // Вершины u и v несмежные
    if(x==0 && t<t[v]+a[v]) //Если для вершины u еще не
    //найден кратчайший путь
    // и новый путь в u короче чем
    //старый, то
    {
    t=t[v]+a[v]; //запоминаем более короткую длину пути в
    //массив t и
    h=v; //запоминаем, что v->u часть кратчайшего
    //пути из s->u
    }
    }

    // Ищем из всех длин некратчайших путей самый короткий
    int w=-infinity; // Для поиска самого короткого пути
    v=-1; // В конце поиска v - вершина, в которую будет
    // найден новый кратчайший путь. Она станет
    // текущей вершиной
    for(u=0;u<p;u++) // Перебираем все вершины.
    {
    if(x==0 && t>w) // Если для вершины не найден кратчайший
    // путь и если длина пути в вершину u меньше
    // уже найденной, то
    {
    v=u; // текущей вершиной становится u-я вершина
    w=t;
    }
    }
    if(v==-1)
    {
    printf("No way from %s to %g.",s,g);

    break;
    }
    if(v==g) // Найден кратчайший путь,
    { // выводим его
    printf("Min way from %i to %i.",s,g);

    u=g;
    while(u!=s)
    {
    printf(" %i",u);
    u=h;
    }
    printf(" %i Way's length - %i",s,t[g]);

    break;
    }
    x[v]=1;
    }
    getch();
    }
     
  4. Гость

    сейчас поняла,что написала полную чушь.ведь диаметр графа-максимальное расстояние между любыми(!) двумя вершинами.есть вообще какой-нибудь стандартный способ поиска диаметра графа?
     
  5. gamecreator

    gamecreator Гость

    может как-то переделать флойда-уоршелла?
     
Загрузка...
Похожие Темы - диаметр графа
  1. rabbit
    Ответов:
    0
    Просмотров:
    1.307
  2. vladis222
    Ответов:
    11
    Просмотров:
    2.555
  3. vladis222
    Ответов:
    4
    Просмотров:
    1.686
  4. vladis222
    Ответов:
    0
    Просмотров:
    1.014

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