Algoritmo de Dijkstra

Algoritmo de Dijkstra

O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos.

Exemplo:

#define MAX_NODES 1024

/* máximo número de nós */

#define INFINITY 1000000000

/* um número maior do que todo o caminho máximo */

int n,dist[MAX_NODES][MAX_NODES];

/*dist[I][j] é a distância de i para j */

void shortest_path(int s,int t,int path[ ])

{struct state

{

/* o caminho em que se trabalha */

int predecessor ;

/*nó prévio */

int length

/*comprimento da fonte até o nó*/

enum {permanent, tentative} label

/*estado do rótulo*/

}state[MAX_NODES];

int I, k, min;

struct state *

p;

for (p=andstate[0];p

p->predecessor=-1

p->length=INFINITY

p->label=tentative;

}

state[t].length=0;

state[t].label=permanent;

k=t; /*k é o nó inicial */

do

{

/* é o melhor caminho de k? */

for I=0; I =0);

}

Algoritmo de Eisenberg e McGuire

Este algoritmo foi publicado em 1972 [EIS 72].

Variáveis globais: quer, dentro: array[n]of boolean;

vez: integer;

Os dois vetores são inicializados com false. Os valores de quer[i] e dentro[i] são alterados apenas pelo processo i, 1≤i≤n. A variável vez assume valores entre 1 e ne seu valor inicial é irrelevante. Cada processo utiliza uma variável local k.

Código do processo i:

. . .

quer[i]:=true;

inicio: dentro[i]:=false;

k:=vez;

loop

if ¬quer[k] then k:=(kmod n)+1

else k:=vez;

exit when k=i

endloop;

dentro[i]:=true;

for k:=1 to nst k≠i

if dentro[k] then goto inicio

endfor; /* Aqui o processo i já garantiu a exclusão mútua, mas vai dar uma última chance ao processo vez. */

if vez≠i and quer[vez] then goto inicio;

vez:=i;

REGIÃO CRÍTICA;

k:=(vezmod n)+1;

loop

exit when quer[k];

k:=(kmod n )+1

endloop;

vez:=k;

quer[i]:=false;

dentro[i]:=false;

. . .

O algoritmo é similar ao de Dijkstra, porém corrigido em relação ao problema da espera limitada. A exclusão mútua é garantida, como antes, através do vetor dentro.

A garantia de progresso é conseguida da seguinte maneira: o valor de vez é alterado apenas quando um processo entra na região crítica (e, mais tarde, quando sai); então, se nenhum processo está entrando ou saindo de sua região crítica, o valor de vez permanece constante; dentre os processos que desejam entrar, o primeiro na ordenação cíclica vez, vez+1, ..., n, 1, 2, ..., vez-1 é o que vai conseguir.

A espera limitada é garantida porque quando um processo deixa a sua região crítica ele designa como seu único sucessor o primeiro processo, dentre os que desejam entrar, na ordem cíclica vez+1, ..., n, 1, 2, ..., vez-1, vez; isto garante que qualquer processo desejando entrar espere no máximo n-1 processos entrar antes dele. Convém observar que, se nenhum processo deseja entrar na sua região crítica, o processo que sai da região crítica faz vez igual ao seu próprio número.

Por motivos didáticos, o algoritmo acima usou os mesmos nomes de variáveis usados pelo algoritmo de Dijkstra. Isto facilita o seu atendimento e deixa claro o relacionamento existente entre os dois algoritmos. O algoritmo original de Eisenberg e McGuire [EIS 72] pode ser encontrado na maioria dos livros de programação concorrente e sistemas operacionais.

Algoritmo Lamport

O princípio é a entrega de um número de atendimento ao cliente como um negócio. É um algoritmo que pode servir para sistemas distribuídos.

Este algoritmo não garante que outros processos não oferecer o mesmo número, neste caso, é nomear primeiro a ser