Archive for the 'algoritmos' Category

Algoritmo de Dijkstra para encontrar o menor caminho em um grafo

Published
by
Vinicius
on July 22, 2007
in algoritmos and resumos
. 0 Comments

Dado um grafo com arestas de peso não-negativo, o algoritmo de Dijkstra encontra o menor caminho possível entre um vértice definido como origem e todos os outros vértices.

Segue uma explicação resumida e “prática” do algoritmo. Para uma referência mais completa, consulte outras páginas.

  1. Criar um array de distâncias (D) com um elemento para cada vértice do grafo e setar o valor zero para o vértice de origem e infinito para os outros vértices;
  2. Criar uma fila de prioridades (Q) com os mesmos valores do array de distâncias, onde a cada requisição deve-se retornar e excluir da fila o vértice de menor distância existente;
  3. Criar um array (P) com um elemento para cada vértice do grafo, setando inicialmente todos os valores como nulo. Este array guardará o vizinho do vértice que faz parte do caminho mínimo.
  4. Enquanto houver elementos em Q:
    1. Extrair um elemento x de Q;
    2. Para cada vizinho y de x, se D[y] for maior do que D[x] + peso(x, y), setar D[y] = Q[y] = D[x] + peso(x, y) e guardar x em P[y].

Ao final, o array D irá conter as distâncias mínimas de cada vértice até a origem. Para obter o caminho mínimo, percorre-se o array P a partir do vértice destino até a origem (P[origem] = nulo).

Partição de inteiros com backtracking

Published
by
Vinicius
on June 1, 2007
in algoritmos, código and programação
. 0 Comments

Dado um inteiro n, uma partição é uma maneira de escrever n como a soma de inteiros positivos. Somas que se diferem somente pela ordem dos números são consideradas as mesmas partições.

O código abaixo, em C, usa backtracking para imprimir a lista de partições de um inteiro lido do teclado.

Para n = 4, a saída é:

1 1 1 1
1 1 2
1 3
2 2
4

Para n = 50, existem 204.226 partições (a 204.217ª é 13 37).

Download do código

#include <stdio.h>

void partition(int *n, int p, int *sum, int *k, int res[])
{
    int i, j;

    for (i=p; i<=*n; i++)
    {
        if ((*sum + i) <= *n)
        {
            *sum+= i;
            res[(*k)++] = i;
            if (*sum == *n)
            {
                for (j=0; j<*k; j++)
                {
                    printf(”%d “, res[j]);
                }
                printf(”\n”);
            }
            else
            {
                partition(n, i, sum, k, res);
            }
            *sum-= i;
            –(*k);
        }
        else
        {
            break;
        }
    }
}

int main()
{
    int sum, k, n, res[100];

    sum = k = 0;

    if (scanf(”%d”, &n) != EOF && n >= 1)
    {
        partition(&n, 1, &sum, &k, res);
    }

    return 0;
}