Complexidade do tempo do algoritmo de Dijkstra
Considere as seguintes cidades: A, B, C, D, E e F conectadas por estradas:
Essas cidades são conectadas por estradas (que podem ser assumidas como retas). O comprimento da estrada da cidade A à cidade B é de 4 unidades; Não é atraído para escalar. O comprimento da estrada da cidade A à cidade C é de 5 unidades; Não é atraído para escalar. O comprimento da cidade B à cidade E é de 11 unidades, não desenhadas para escalar. As estradas entre outras cidades são indicadas da mesma forma.
As cidades: A, B, C, D, E e F são os vértices de um gráfico. As estradas são as bordas do gráfico. No entanto, este gráfico será representado em uma estrutura de dados matemática, diferentemente de seu layout geográfico.
O algoritmo de Dijkstra pode ser usado para encontrar o caminho mais curto entre um vértice de origem (digamos A) e qualquer outro vértice. Para mais simplicidade, este artigo terá como objetivo procurar o caminho mais curto de A a E.
Existem diferentes caminhos de A a E, com comprimentos diferentes, como segue:
A-B-D-F: 4 + 9 + 2 = 15A-b-e-f: 4 + 7 + 6 = 17
A-B-C-E-F: 4 + 11 + 3 + 6 = 24
A-B-C-E-D-F: 4 + 11 + 3 + 13 + 2 = 33
A-b-d-e-f: 4 + 9 + 13 + 6 = 32
A-B-E-D-F: 4 + 7 + 13 + 2 = 26
A-C-E-F: 5 + 3 + 6 = 14
A-C-B-D-F: 5 + 11 + 9 + 2 = 27
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-E-D-F: 5 + 3 + 13 + 2 = 14
A-C-B-E-D-F: 5 + 11 + 7 + 13 + 2 = 38
A partir desta listagem, o caminho mais curto é A-C-e-F, com um comprimento total de 14 unidades.
O principal objetivo deste artigo é encontrar o tempo de execução do algoritmo de Dijkstra para obter o caminho mais curto de A a E. O tempo não será dado em segundos ou minutos. É o tempo de execução total relativo, chamado de complexidade do tempo, que será dado. A codificação C ++ também é fornecida.
Gráfico para usar
A complexidade do tempo (tempo de execução relativa) depende principalmente do tipo de gráfico matemático usado para representar o layout geográfico. Depende também do algoritmo (outro tipo de algoritmo) usado para classificar os vértices vizinhos de cada vértice no algoritmo geral (algoritmo de Dijkstra). A classificação dos vértices vizinhos não é abordada neste artigo.
O gráfico matemático escolhido para este artigo é chamado de matriz de adjacência. Isso é:
Os cabeçalhos da linha são os nomes das cidades de A a F. Os cabeçalhos da coluna são os mesmos nomes de cidades de A a F. Cada entrada é a duração de uma estrada de uma cidade para a próxima. A duração de uma estrada de uma cidade a si mesma é zero. A duração de uma estrada de uma cidade para outra, depois de pular uma ou mais cidades, também é zero. Apenas estradas diretas são consideradas. Cada entrada está localizada, primeiro por linha e depois por coluna. Novamente, cada entrada é o comprimento de uma estrada, sem pular uma cidade, e não para a própria cidade. Esta matriz é uma representação matemática da rede geográfica dada acima.
Portanto, a matriz consiste em bordas, com os cabeçalhos de linha e coluna dos mesmos vértices. A matriz é a principal estrutura necessária no programa. Dois outros vetores (matrizes) são usados neste programa básico.
Algoritmo de Dijkstra
O algoritmo de Dijkstra procura o caminho mais curto entre dois vértices em um gráfico (rede). A matriz acima é o gráfico, que corresponde à rede geográfica acima. Por simplicidade, o programa neste artigo procurará o caminho mais curto entre um vértice de origem e um vértice de destino. Precisamente, o programa procurará o caminho mais curto do vértice da fonte, a, até o vértice de destino, f.
O algoritmo, como relevante para esta tarefa, é o seguinte:
- Todos os vértices são marcados como não visitados. Neste ponto, um conjunto de todos os vértices não visitados são criados.
- Atribua um valor tentativo do comprimento do caminho a todos os vértices: o comprimento do caminho da fonte para a fonte recebe um valor de zero; O comprimento do caminho da fonte para qualquer outro vértice é atribuído o valor único do infinito, i.e., um valor maior que o caminho mais alto possível, no gráfico. O valor de cada vértice seria alterado pelo menos uma vez, de um valor alto para um valor mais baixo, à medida que o algoritmo continua. Os possíveis vértices para o caminho mais curto completo serão focados, começando a partir do vértice da fonte (a). O vértice com o foco é chamado de vértice atual. O vértice atual tem vizinhos, melhor visualizados a partir da rede real (layout geográfico) acima.
- Existe o vértice atual, e há o vértice visitado. De fato, haveria mais de um vértice visitado em uma cadeia enquanto o algoritmo continua. Todos os vértices anteriores considerados visitados estão no caminho mais curto que está sendo desenvolvido, começando a partir da fonte. O comprimento do caminho do último vértice visitado é conhecido (deve ser conhecido). Um vértice é declarado visitado quando seu comprimento de caminho é confirmado. O vértice visitado fornece o menor comprimento do caminho da fonte até agora, pois o algoritmo está em andamento. Os vizinhos não visitados do vértice atual, exceto seu vizinho visitado anterior imediato, têm valores tentativos (comprimentos do caminho da fonte), alguns dos quais ainda podem ser infinitos (valor muito alto). Para cada vizinho não visitado e o vértice atual, um novo comprimento de caminho tentativo é calculado da seguinte forma: o comprimento do caminho do vértice visitado anteriormente, além do comprimento da borda do vértice atual, mais o comprimento da borda do vértice atual, para o vizinho não visitado. Se esse resultado for menor do que o que estava lá, como o comprimento do caminho provisório da fonte ao vizinho não visitado do vértice atual, esse valor calculado se torna o novo valor tentativo para o vizinho do vértice atual. Ou seja, o novo valor de caminho provisório para um vértice não visitado é calculado através do vértice atual do vértice visitado anteriormente.
- Pode haver mais de um vértices atuais. Quando todos os vizinhos de cada vértice atuais foram acessados e recebem novos comprimentos de caminho tentativo apropriado, o vértice atual com o menor comprimento do caminho da fonte (menor valor) é considerado visitado. Como tinha o menor valor, o menor valor é confirmado como o comprimento mais curto do caminho da peça até agora. O vértice visitado anteriormente é removido do conjunto de vértice não visitado. Um vértice visitado nunca será verificado novamente. Quaisquer visitas depois teriam um comprimento de caminho maior.
- As duas etapas anteriores são repetidas, para qualquer próximo vértice atual que se torne um vértice visitado. Esta repetição continua até que o vértice de destino seja alcançado. O vértice de destino pode ser qualquer vértice após o vértice da fonte. No entanto, por simplicidade, o último vértice, f da rede acima, foi escolhido como o vértice de destino para este artigo.
- À medida que o algoritmo avança, cada vértice de cada pai (visitado anteriormente) e cada criança (visitada em seguida) do caminho mais curto devem ser registrados no caso de o caminho mais curto, por vértices, bem como o caminho mais curto por comprimento, é necessário (é necessária ( solicitado). Quando o vértice de destino é alcançado e visitado, o caminho mais curto completo pode ser rastreado para trás se o caminho pelos vértices for necessário. Quanto ao comprimento do caminho, foi calculado à medida que o algoritmo progredia.
Ilustração Algoritmo de Dijkstra
A estrada acima
A rede é usada para ilustrar o algoritmo de Dijkstra. É re-exibido abaixo para facilitar a referência.
Começa na fonte, "A" com um comprimento de caminho de zero. "A" é considerado visitado e removido da lista não visitada (conjunto). "A" é enviado para uma lista visitada, caso o caminho pelos vértices seja necessário.
Os comprimentos do caminho de A a B são:
A-b = 4A-C-B = 5 + 11 = 16
Entre 4, 16 e infinito (que estava lá), 4 é o mínimo. Então, B recebe o valor provisório de 4 como comprimento do caminho.
Os comprimentos do caminho de A a C são:
A-C = 5A-b-c = 4 + 11 = 15
Entre 5, 15 e infinito (que estava lá), 5 é o mínimo. Então, C recebe o valor provisório de 5 como comprimento do caminho.
B e C eram os vizinhos não visitados de um. Atualmente, cada um tem um comprimento de caminho provisório. Entre B e C, um vértice deve ser escolhido contribuir para o caminho geral final. B e C também têm vizinhos.
Os vizinhos não visitados de B são D, E e C, com comprimentos infinitos provisórios. Os vizinhos não visitados de C são B e E com comprimentos infinitos tentativos. Um vizinho tem uma vantagem direta do vértice em questão.
O comprimento do caminho calculado de A a D, através de B é:
A-b-d = 4 + 9 = 13O comprimento do caminho calculado de A a E, através de B é:
A-b-e = 4 + 7 = 11O comprimento do caminho calculado de A a C, através de B é:
A-b-c = 4 + 11 = 15Esses são os comprimentos do caminho através dos vizinhos de B para B, do vértice visitado, “a”. Os comprimentos de caminho provisório através de C também devem ser determinados.
O comprimento do caminho calculado de A a B, através de C é:
A-C-B = 5 + 11 = 16O comprimento do caminho calculado de A a E a C é:
A-c-e = 5 + 3 = 8Esses são os comprimentos do caminho através dos vizinhos de C a C, do vértice visitado, "a".
Todos os comprimentos provisórios calculados do caminho da peça até agora são:
A-b-d = 4 + 9 = 13A-b-e = 4 + 7 = 11
A-b-c = 4 + 11 = 15
A-C-B = 5 + 11 = 16
A-c-e = 5 + 3 = 8
O mais curto desses comprimentos de path parcial é:
A-c-e = 5 + 3 = 8Então o vértice, C, é escolhido para o caminho a seguir. Este é o próximo vértice visitado. Qualquer caminho possível através de B é abandonado. C é então considerado visitado. O vértice C é removido da lista não visitada. C é enviado para a lista visitada (para ser A após a).
C deve ter vizinhos não visitados com comprimentos de caminho provisórios. Nesse caso, é B e E. B tem vizinhos com comprimentos de caminho infinito, que são d e e. E tem vizinhos com comprimentos de caminho infinito, que são d e f. Para escolher o próximo nó visitado, os comprimentos provisórios do caminho da peça de C a B e E devem ser calculados. Os cálculos são:
A-C-B-D = 5 + 11 + 9= 16 + 9 = 25
A-c-b-e = 5 + 11 + 7
= 16 + 7 = 23
A-c-e-d = 5 + 3 + 13
= 8 + 13 = 21
A-c-e-f = 5 + 3 + 6
= 8 + 6 = 14
O mais curto para esses caminhos de peças é:
A-c-e-f = 8 + 6 = 14Neste ponto, E é o caminho a seguir. Este é o próximo vértice visitado. Qualquer caminho possível através de D é abandonado. E é removido da lista não visitada e adicionado à lista visitada (para ser C).
E tem vizinhos não visitados com comprimentos de caminho provisórios. Nesse caso, é D e F. Se F tivesse vizinhos não visitados, seus comprimentos de caminho provisório de "A", a fonte, deveriam ter sido infinitos. Agora, o comprimento de F a nada é 0. Para escolher o próximo nó visitado (vértice), os comprimentos provisórios do caminho da peça de E a D e E a F devem ser calculados. Os cálculos são:
A-C-E-D-F = 5 + 3 + 13 + 2= 8 + 15 = 23
A-c-e-f- = 5 + 3 + 6 + 0
= 14 + 0 = 14
O mais curto desses comprimentos de path parcial é:
A-c-e-f- = 14Neste ponto, F é o caminho a seguir. É considerado visitado. F é removido da lista não visitada e adicionado à lista visitada (para ser e depois de e).
F é o destino. E assim, o comprimento do caminho mais curto da fonte, a, para o destino, f, é 14. Os vértices e sua ordem na lista visitada devem ser A-C-e-F. Este é o caminho mais curto para a frente dos vértices. Para obter o caminho mais curto reverso pelos vértices, leia a lista para trás.
Codificação C ++
O gráfico
O gráfico para a rede é uma matriz bidimensional. Isso é:
int g [v] [v] = 0,4,5,0,0,0,4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
Deve ser codificado na função principal C ++. Cada entrada é o comprimento da borda de um vértice, lido por linhas, para o próximo vértice, lido por colunas. Esse valor não é para mais de um par de vértices.
Vértices como números
Por conveniência, os vértices serão identificados por números, usando codificação ASCII, como segue:
A é 65B é 66
C é 67
D é 68
E é 69
F é 70
A é 0 + 65 = 65
B é 1 + 65 = 65
C é 2 + 65 = 65
D é 3 + 65 = 65
E é 4 + 65 = 65
F é 5 + 65 = 65
Os valores de codificação para A, B, C, D, E e F são os seguintes:
A = 0B = 1
C = 2
D = 3
E = 4
F = 5
65 serão adicionados a cada um desses números para obter o número ASCII correspondente, do qual a letra correspondente será obtida.
Início do programa
O início do programa é:
#incluir#incluir
usando namespace std;
int int_max = +2'147'483'647; //infinidade
#Define v 6 // Número de vértice em G
int ShortStLength = int_max;
vetor não visitado = 0, 1, 2, 3, 4, 5;
VectorVisited;
O valor para o infinito escolhido pelo programador é 2147483647. O número de vértices, v (na mancha), é definido (atribuído) como 6. Os elementos do vetor não visitado (matriz) são A, B, C, D, E e F, como 0, 1, 2, 3, 4, 5, correspondentes aos números do código ASCII 65, 66, 67, 68, 69, 70. Esta ordem, neste caso, não é necessariamente uma ordem predeterminada e classificada. Os vértices visitados serão empurrados para o vetor visitado na ordem descoberta pelo algoritmo, começando com o vértice da fonte.
A função getNeighbors ()
Esta função obtém todos os vizinhos à frente de um vértice, começando logo após o vértice relacionado visitado anteriormente. O código da função é:
Vectorgetneighbors (Int Graph [V] [V], int Vindx, int prevvisitedindx)vectorneighbors;
for (int j = prevvisitedindx+1; j; j;
vizinhos.push_back (j);
retornar vizinhos;
A função dijkstra ()
Depois que o índice de origem (vértice) foi considerado pelo programa, a função dijkstra () entra em ação recursivamente até que o índice de destino (vértice) seja considerado. O código da função é:
Void Dijkstra (Int Graph [V] [v], int visitedIdx, int visitLength)int visitedIndx = visitedIdx;
int newVisitedindx = v;
int minLength = int_max;
Int VisitedLength;
int tentLength1 = 0;
VectorVisitedNBs = getNeighbors (gráfico, visitedIndx, visitedIdx);
para (int i = 0; i
VectorCurrentNBs = getNeighbors (gráfico, visitednbs [i], visitedidx);
if (currentnbs.tamanho() != 0)
for (int j = 0; j
if (tentLength2
newVisitedindx = visitednbs [i];
outro
VisitedLength = TentLength1; //confirmado
newVisitedindx = visitednbs [i];
visitedIndx = newVisitedIndx;
não visitado [visitedIndx] = -1;
visitado.push_back (visitedindx);
curto comprimento = VisitedLength;
if (visitedindx< V -1)
Dijkstra (gráfico, visitoundx, visitado);
A função startdijkstra ()
O algoritmo do Dijkstra começa com esta função para lidar com a situação do código -fonte. O código da função é:
Void StartDijkstra (Int Graph [V] [V], int srcVidx)int visitedIndx = srcVidx;
não visitado [visitedIndx] = -1;
visitado.push_back (visitedindx);
int visitedLength = 0;
Dijkstra (gráfico, visitoundx, visitado);
Os segmentos de código acima podem ser montados na ordem dada para formar o programa.
A função principal C ++
Uma função principal C ++ adequada é:
int main (int argc, char ** argv)int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
int fontesvertex = 0;
startdijkstra (G, Sourcevertex);
cout<
cout<
Conclusão
A complexidade do tempo é o tempo de execução relativo. Supondo que a classificação dos vértices (vizinhos) seja boa, diz -se que o programa acima possui a complexidade seguinte:
O ((| e | + | v |) log | v |)onde | e | é o número de bordas, | v | é o número de vértices e um log é o log2. O Big-O com seus colchetes, () é uma maneira de indicar que a expressão nos parênteses é a complexidade do tempo (tempo de execução relativo).
A pior complexidade do tempo para o algoritmo de Dijkstra é: O (| V |2)
[/cc]