Алгоритм Дейкстры и цикл for (для заполнения веса рёбер графа) - C (СИ)
Формулировка задачи:
Здравствуйте. Задался я написанием алгоритма Дейкстры, но возникла проблема в одном цикле
Граф заполняется при помощи матрицы (двумерного массива) размерности NxN, где В принципе всё работает вполне нормально (прикреплённая анимация 1)
Но, если после первого то цикл начинает работать неправильно (прикреплённая анимация 2).
Как видно на анимации — появляются петли.
Расскажите мне нубу и индусу, почему фигурные скобки так ломают результат?
for
. Чтобы не испытывать ваши телепатические способности, я постараюсь как можно подробнее описать, в чем же заключается проблема. Для начала скажу, что граф в коденеориентированный
и в нем нетпетель
.Не по теме:
То бишь переход [1]―[2] имеет тот же «вес», что и [2]―[1]. А та же нет переходов вида [3]―[3] (петель). Ну это всем очевидно, но на всякий случай написал.
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
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
Решение задачи: «Алгоритм Дейкстры и цикл 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
Объяснение кода листинга программы
- Задана матрица (граф) MatSmezh размером height x width.
- В первом цикле for (i = 1; i <= height; i++) для каждой вершины графа (строки матрицы) устанавливается начальное значение веса рёбер равное 0.
- Во втором цикле for (i = 1; i <= height; i++) для каждой вершины графа (строки матрицы) происходит ввод значений весов рёбер, соединяющих вершину с остальными вершинами графа (j = i + 1; j <= width).
- Введенное значение веса рёбер записывается в матрицу MatSmezh, а также в матрицу MatSmezh, но уже в столбец, соответствующий вершине, с которой соединяется текущая вершина.
- В следующем элементе кода выводятся все значения матрицы MatSmezh, которые не равны 0.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д