Алгоритм Флойда Варшалла и сеточные графы - PullRequest
Новая
       109

Алгоритм Флойда Варшалла и сеточные графы

0 голосов
/ 01 июня 2018

Используя псевдокод, найденный в википедии, для реализации алгоритма Флойда Уоршалла в представлении списка смежности был создан следующий код.Граф является сеткой, поэтому, если это 3 × 3, у вершины 0 есть два ребра, а у вершины 1 - 3, а у вершины 2 - два и т. Д.

self-> V = количество вершин вgraph !! 

void floyd(Graph *self, int** dist, int** next)
{
    int i, j, k;
    EdgeNodePtr current;

    current =  malloc(sizeof(current));

    for (i = 0; i < self->V; i++)
    {
        for (j = 0; j < self->V; j++) {
            dist[i][j] = INT_MAX; // Sets all minimun distances to infintiy
            next[i][j] = -1; // Sets all next vertex to a non existant vertex
        }
    }

    for (i = 0; i < self->V; i++)
    {
        for (j = 0; j < self->V; j++)
        {
            current = self->edges[i].head;

            while (current != NULL) // Cycles through all the edges in edgelist
            {
                if (current->edge.to_vertex == j) // If an edge to the correct vertex is found then adds distance
                {
                    dist[i][j] = current->edge.weight;
                    next[i][j] = j; // Updates next node
                }
                current =  current->next;
            }

        }
    }

    PRINT

    // Standard implemnation of floyds algorithm
    for (k = 0; k < self->V; k++)
    {
        for (i = 0; i < self->V; i++)
        {
            for (j = 0; j < self->V; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
 PRINT
}

Что происходит, если все ребра правильно вставляются в массив расстояний, проверяется простым шрифтом.Проблема возникает, когда алгоритм работает, он превращает все расстояния в INT_MINS или аналогичные числа.Хотя на самом деле не рассчитываются расстояния.

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

Aизображение вывода из печати списка графа, где написано PRINT enter image description here

1 Ответ

0 голосов
/ 01 июня 2018

Вы должны быть осторожны с переполнением int.Псевдокод Википедии (внизу этого ответа) использует "бесконечность", где "бесконечность + (что-либо конечное) = бесконечность".Однако это не тот случай, когда вы используете INT_MAX для представления «бесконечности» из-за переполнения.Попробуйте изменить условие if на: 

if (dist[i][k] != INT_MAX &&
         dist[k][j] != INT_MAX &&
         dist[i][j] > dist[i][k] + dist[k][j]) {

Это позволит избежать переполнения int при добавлении положительного расстояния к INT_MAX.

Псевдокод Википедии: 

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if
...