Diferença entre algoritmos de Prim e de Dijkstra?

Qual é a diferença exata entre os algoritmos de Dijkstra e Prim? Eu sei que o Prim vai dar um MST, mas a árvore gerada por Dijkstra também será um MST. Então, qual é a diferença exata?

O algoritmo de Prim constrói uma árvore geradora mínima para o gráfico, que é uma árvore que conecta todos os nós no gráfico e tem o menor custo total entre todas as árvores que conectam todos os nós. No entanto, o comprimento de um caminho entre quaisquer dois nós no MST pode não ser o caminho mais curto entre esses dois nós no gráfico original. Os MSTs são úteis, por exemplo, se você quiser conectar fisicamente os nós no gráfico para fornecer eletricidade a eles com o menor custo total. Não importa que o comprimento do caminho entre dois nós não seja o ideal, já que tudo o que importa é o fato de eles estarem conectados.

O algoritmo de Dijkstra constrói uma árvore de caminho mais curto começando em algum nó de origem. Uma árvore de caminho mais curto é uma árvore que conecta todos os nós no gráfico de volta ao nó de origem e tem a propriedade de minimizar o comprimento de qualquer caminho do nó de origem a qualquer outro nó do gráfico. Isso é útil, por exemplo, se você deseja construir uma rede de estradas que torne o mais eficiente possível para todos chegarem a algum ponto importante. No entanto, a árvore do caminho mais curto não tem garantia de ser uma árvore de abrangência mínima, e a soma dos custos nas arestas de uma árvore do caminho mais curto pode ser muito maior do que o custo de um MST.

Outra diferença importante diz respeito aos tipos de gráficos nos quais os algoritmos funcionam. O algoritmo de Prim funciona apenas em gráficos não direcionados, uma vez que o conceito de um MST assume que os gráficos são inerentemente não direcionados. (Existe algo chamado "arborescência de abrangência mínima" para gráficos direcionados, mas os algoritmos para encontrá-los são muito mais complicados). O algoritmo de Dijkstra funcionará bem em gráficos direcionados, uma vez que as árvores de caminho mais curto podem de fato ser direcionadas. Além disso, o algoritmo de Dijkstra não produz necessariamente a solução correta em gráficos contendo pesos de aresta negativos , enquanto o algoritmo de Prim pode lidar com isso.

Espero que isto ajude!

O algoritmo de Dijkstra não cria um MST, ele encontra o caminho mais curto.

Considere este gráfico

       5     5
  s *-----*-----* t
     \         /
       -------
         9

O caminho mais curto é 9, enquanto o MST é um 'caminho' diferente em 10.

Os algoritmos Prim e Dijkstra são quase os mesmos, exceto para a "função de relaxamento".

Prim:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

A única diferença é apontada pela seta, que é a função relaxar.

• O Prim, que busca a árvore geradora mínima, só se preocupa com o mínimo das arestas totais que cobrem todos os vértices. A função de relaxamento éalt = w(u,v)
• O Dijkstra, que busca o comprimento mínimo do caminho, por isso se preocupa com o acúmulo de arestas. A função de relaxamento éalt = w(u,v) + u.key

O algoritmo de Dijsktra encontra a distância mínima do nó i a todos os nós (você especifica i). Então, em troca, você obtém a árvore de distância mínima do nó i.

O algoritmo Prims fornece a árvore de abrangência mínima para um determinado gráfico . Uma árvore que conecta todos os nós enquanto a soma de todos os custos é o mínimo possível.

Então, com Dijkstra você pode ir de um nó selecionado para qualquer outro com o custo mínimo , você não consegue isso com Prim's

A única diferença que vejo é que o algoritmo de Prim armazena uma borda de custo mínimo, enquanto o algoritmo de Dijkstra armazena o custo total de um vértice de origem até o vértice atual.

Dijkstra fornece um caminho do nó de origem ao nó de destino de forma que o custo seja mínimo. No entanto, o algoritmo de Prim fornece uma árvore de abrangência mínima de forma que todos os nós estão conectados e o custo total é mínimo.

Em palavras simples:

Então, se você deseja implantar um trem para conectar várias cidades, você usaria o algoritmo de Prim. Mas se você quiser ir de uma cidade a outra economizando o máximo de tempo possível, use o algoritmo de Dijkstra.

Ambos podem ser implementados usando exatamente o mesmo algoritmo genérico da seguinte maneira:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Para Prim, passe f = w(u, v)e para Dijkstra pass f = u.key + w(u, v).

Outra coisa interessante é que o Genérico acima também pode implementar Breadth First Search (BFS), embora seja um exagero porque a fila de prioridade cara não é realmente necessária. Para transformar o algoritmo genérico acima do BFS, passe o f = u.key + 1que é o mesmo que impor todos os pesos a 1 (isto é, o BFS fornece o número mínimo de arestas necessárias para atravessar do ponto A ao B).

Intuição

Aqui está uma boa maneira de pensar sobre o algoritmo genérico acima: Começamos com dois depósitos A e B. Inicialmente, coloque todos os seus vértices em B para que o depósito A fique vazio. Em seguida, movemos um vértice de B para A. Agora olhe para todas as arestas dos vértices em A que se cruzam para os vértices em B. Escolhemos uma aresta usando alguns critérios dessas arestas cruzadas e movemos o vértice correspondente de B para A. Repita este processo até que B esteja vazio.

Uma forma de força bruta de implementar essa ideia seria manter uma fila de prioridade das arestas para os vértices em A que cruza para B. Obviamente, isso seria problemático se o gráfico não fosse esparso. Então a questão seria: podemos, em vez disso, manter a fila de prioridade de vértices? Isso de fato podemos, pois nossa decisão final é qual vértice escolher de B.

Contexto histórico

É interessante que a versão genérica da técnica por trás de ambos os algoritmos seja conceitualmente tão antiga quanto 1930, mesmo quando os computadores eletrônicos não existiam.

A história começa com Otakar Borůvka, que precisava de um algoritmo para um amigo da família tentando descobrir como conectar cidades no país da Morávia (agora parte da República Tcheca) com linhas elétricas de custo mínimo. Ele publicou seu algoritmo em 1926 em um jornal relacionado à matemática, já que a Ciência da Computação ainda não existia. Isso chamou a atenção de Vojtěch Jarník, que pensou em uma melhoria no algoritmo de Borůvka e o publicou em 1930. Ele de fato descobriu o mesmo algoritmo que agora conhecemos como algoritmo de Prim que o redescobriu em 1957.

Independente de tudo isso, em 1956 Dijkstra precisava escrever um programa para demonstrar as capacidades de um novo computador desenvolvido por seu instituto. Ele achou que seria legal que o computador encontrasse conexões para viajar entre duas cidades da Holanda. Ele projetou o algoritmo em 20 minutos. Ele criou um gráfico de 64 cidades com algumas simplificações (porque seu computador era de 6 bits) e escreveu o código para este computador de 1956. No entanto, ele não publicou seu algoritmo porque basicamente não havia periódicos de ciência da computação e ele achou que isso pode não ser muito importante. No ano seguinte, ele aprendeu sobre o problema de conectar terminais de novos computadores de forma que o comprimento dos fios fosse minimizado. Ele pensou sobre este problema e redescobriu Jarník / Prim ' s algoritmo que novamente usa a mesma técnica que o algoritmo de caminho mais curto que ele descobriu um ano antes. Elemencionou que ambos os algoritmos foram projetados sem o uso de caneta ou papel. Em 1959, ele publicou os dois algoritmos em um artigo de apenas 2 páginas e meia.

Dijkstra encontra o caminho mais curto entre seu nó inicial e todos os outros nós. Então, em troca, você obtém a árvore de distância mínima do nó inicial, ou seja, você pode alcançar todos os outros nós da maneira mais eficiente possível.

O algoritmo Prims fornece o MST para um dado gráfico, ou seja, uma árvore que conecta todos os nós enquanto a soma de todos os custos é o mínimo possível.

Para encurtar a história com um exemplo realista:

1. Dijkstra quer saber o caminho mais curto para cada ponto de destino, economizando tempo de viagem e combustível.
2. Prim quer saber como implantar com eficiência um sistema ferroviário, ou seja, economizando custos de material.

Diretamente do artigo da wikipedia de Dijkstra's Algorithm :

O processo subjacente ao algoritmo de Dijkstra é semelhante ao processo ganancioso usado no algoritmo de Prim. O propósito de Prim é encontrar uma árvore de abrangência mínima que conecte todos os nós no gráfico; Dijkstra está preocupado apenas com dois nós. O Prim's não avalia o peso total do caminho a partir do nó inicial, apenas o caminho individual.

Eu estava incomodado com a mesma pergunta recentemente, e acho que posso compartilhar meu entendimento ...

Acho que a principal diferença entre esses dois algoritmos (Dijkstra e Prim) está no problema que eles foram projetados para resolver, ou seja, o caminho mais curto entre dois nós e a árvore geradora mínima (MST). O formal é para encontrar o caminho mais curto entre digamos, nó s e t , e uma exigência racional é visitar cada aresta do gráfico no máximo uma vez. No entanto, NÃO exige que visitemos todo o nó. O último (MST) é para nos fazer visitar TODOS os nodos (no máximo uma vez), e com a mesma exigência racional de visitar cada borda no máximo uma vez também.

Dito isso, Dijkstra nos permite "pegar um atalho" até que eu consiga ir de s até t , sem nos preocupar com as consequências - quando chegar a t , pronto! Embora haja também um caminho de s para t no MST, mas esse caminho s - t é criado considerando todos os nós restantes, portanto, esse caminho pode ser mais longo do que o caminho s - t encontrado pelo algoritmo de Dijstra. Abaixo está um exemplo rápido com 3 nós:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Digamos que cada uma das arestas superiores tenha o custo de 2 e a aresta inferior tenha um custo de 3, então Dijktra nos dirá para tomar o caminho inferior, já que não nos importamos com o nó do meio. Por outro lado, Prim nos retornará um MST com as 2 bordas superiores, descartando a borda inferior.

Essa diferença também se reflete na diferença sutil nas implementações: no algoritmo de Dijkstra, é necessário ter uma etapa de contabilidade (para cada nó) para atualizar o caminho mais curto de s , após absorver um novo nó, enquanto no algoritmo de Prim, há não é essa necessidade.

A principal diferença entre os algoritmos básicos está em seus diferentes critérios de seleção de arestas. Geralmente, ambos usam uma fila de prioridade para selecionar os próximos nós, mas têm critérios diferentes para selecionar os nós adjacentes dos nós de processamento atuais: o algoritmo de Prim requer que os próximos nós adjacentes também sejam mantidos na fila, enquanto o algoritmo de Dijkstra não:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Os cálculos de vertex.distance são o segundo ponto diferente.

O algoritmo de Dijkstra é um problema de caminho mais curto de fonte única entre os nós i e j, mas o algoritmo de Prim é um problema de árvore geradora mínima. Este algoritmo usa o conceito de programação denominado 'algoritmo guloso'

Se você verificar essas noções, visite

1. Nota de aula sobre algoritmo ganancioso: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Árvore de abrangência mínima: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Caminho mais curto de fonte única: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

O algoritmo de Dijkstras é usado apenas para encontrar o caminho mais curto.

Na árvore de abrangência mínima ( algoritmo de Prim ou Kruskal) você obtém egdes mínimos com valor mínimo de borda.

Por exemplo: - Considere uma situação em que você não deseja criar uma rede enorme para a qual você precisará de um grande número de fios, de modo que a contagem de fios pode ser feita usando a árvore de abrangência mínima (algoritmo de Prim ou Kruskal) (ou seja, irá fornecem um número mínimo de fios para criar uma grande conexão de rede com fio com custo mínimo).

Já o "algoritmo de Dijkstras" será usado para obter o caminho mais curto entre dois nós enquanto conecta quaisquer nós entre si.

A explicação mais simples é em Prims que você não especifica o nó inicial , mas em dijsktra você (precisa ter um nó inicial) tem que encontrar o caminho mais curto do nó fornecido para todos os outros nós.

@templatetypedef cobriu a diferença entre o MST e o caminho mais curto. Eu cobri a diferença do algoritmo em outra resposta So , demonstrando que ambos podem ser implementados usando o mesmo algoritmo genérico que leva mais um parâmetro como entrada: função f(u,v). A diferença entre o algoritmo de Prim e Dijkstra é simplesmente o que f(u,v)você usa.

No nível do código, a outra diferença é a API.

Você inicializa o Prim com um vértice de origem, s , ou seja Prim.new(s),; s pode ser qualquer vértice e, independentemente de s , o resultado final, que são as arestas da árvore de abrangência mínima (MST), são os mesmos. Para obter as bordas do MST, chamamos o método edges().

Você inicializa Dijkstra com um vértice de origem, s , ou seja, Dijkstra.new(s)deseja obter o caminho / distância mais curta para todos os outros vértices. Os resultados finais, que são o caminho / distância mais curta de s para todos os outros vértices; são diferentes dependendo do s . Para obter os caminhos / distâncias mais curtos de s a qualquer vértice, v , chamamos os métodos distanceTo(v)e pathTo(v)respectivamente.