Алгоритм Дейкстры и цикл for (для заполнения веса рёбер графа) - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте. Задался я написанием алгоритма Дейкстры, но возникла проблема в одном цикле

for

. Чтобы не испытывать ваши телепатические способности, я постараюсь как можно подробнее описать, в чем же заключается проблема. Для начала скажу, что граф в коде

неориентированный

и в нем нет

петель

.

Не по теме:

То бишь переход [1]―[2] имеет тот же «вес», что и [2]―[1]. А та же нет переходов вида [3]―[3] (петель). Ну это всем очевидно, но на всякий случай написал.

Граф заполняется при помощи матрицы (двумерного массива) размерности NxN, где

N

— число вершин графа. А элемент

Аij

в матрице — «вес» ребра (перехода). Если вес равен 0, то перехода нет. И отрицательного «веса» быть не может. К вашему вниманию предоставляю элемент кода, в котором происходит заполнение графа: MatSmezh[i][j] — это как раз наш двумерный массив.
for(i = 1; i <= height; i++)    //height = width (матрица квадратная) 
    for(j = 1; j <= width; j++)
        MatSmezh[i][j] = 0;     //изначально всем рёбрам присваивается 0
        for(i = 1; i <= height; i++)    //этот цикл, чтобы после ввода, например, [1]-[2] не нужно было вводить [2]-[1]
        {
            for(j = i+1; j <= width; j++)
        {   
            printf("From [%d] to [%d] = ", i, j);   
            scanf_s("%d", &MatSmezh[i][j]);     //ввод значений (веса рёбер) массива
            MatSmezh[j][i] = MatSmezh[i][j];    //[i]-[j] имеет тот же вес, что и [j]-[i]
        }
        }
 
   //дальше, в следующем элементе кода выводятся всё значения не равные 0
В принципе всё работает вполне нормально (прикреплённая анимация 1) Но, если после первого

for

и второго

for

поставить фигурные скобки (ну и в конце кода тоже),
for(i = 1; i <= height; i++)    //height = width (матрица квадратная) 
{
    for(j = 1; j <= width; j++)
    {
        MatSmezh[i][j] = 0;     //изначально всем рёбрам присваивается 0
        for(i = 1; i <= height; i++)    //этот цикл, чтобы после ввода, например, [1]-[2] не нужно было вводить [2]-[1]
        {
            for(j = i+1; j <= width; j++)
        {   
            printf("From [%d] to [%d] = ", i, j);   
            scanf_s("%d", &MatSmezh[i][j]);     //ввод значений (веса рёбер) массива
            MatSmezh[j][i] = MatSmezh[i][j];    //[i]-[j] имеет тот же вес, что и [j]-[i]
        }
        }
    }
}
 
   //дальше, в следующем элементе кода выводятся всё значения не равные 0
то цикл начинает работать неправильно (прикреплённая анимация 2). Как видно на анимации — появляются петли. Расскажите мне нубу и индусу, почему фигурные скобки так ломают результат?

Решение задачи: «Алгоритм Дейкстры и цикл for (для заполнения веса рёбер графа)»

textual
Листинг программы
for (i = 1; i <= height; i++)    //height = width (матрица квадратная)
    for(j = 1; j <= width; j++)
        MatSmezh[i][j] = 0;     //изначально всем рёбрам присваивается 0
        
        
for (i = 1; i <= height; i++)    //этот цикл, чтобы после ввода, например, [1]-[2] не нужно было вводить [2]-[1]    {
    for(j = i + 1; j <= width; j++)
    {
        printf("From [%d] to [%d] = ", i, j);
        scanf("%d", &MatSmezh[i][j]);     //ввод значений (веса рёбер) массива
        MatSmezh[j][i] = MatSmezh[i][j];    //[i]-[j] имеет тот же вес, что и [j]-[i]
    }
 
   //дальше, в следующем элементе кода выводятся всё значения не равные 0

Объяснение кода листинга программы

  1. Задана матрица (граф) MatSmezh размером height x width.
  2. В первом цикле for (i = 1; i <= height; i++) для каждой вершины графа (строки матрицы) устанавливается начальное значение веса рёбер равное 0.
  3. Во втором цикле for (i = 1; i <= height; i++) для каждой вершины графа (строки матрицы) происходит ввод значений весов рёбер, соединяющих вершину с остальными вершинами графа (j = i + 1; j <= width).
  4. Введенное значение веса рёбер записывается в матрицу MatSmezh, а также в матрицу MatSmezh, но уже в столбец, соответствующий вершине, с которой соединяется текущая вершина.
  5. В следующем элементе кода выводятся все значения матрицы MatSmezh, которые не равны 0.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

13   голосов , оценка 4.077 из 5
Похожие ответы