Algoritmo de Dijkstra - Explicação e Aplicação em Grafos

ESTRUTURA DE DADOS II Prof Eugênio Júlio Messala Cândido Carvalho eugeniojuliomesslagmailcom 62 992410579 16a ATIVIDADE Grafos Algoritmo de Dijkstra GRAFO ALGORITMO DE DIJKSTRA Este algoritmo foi criado por Edsger Disjkstra em 1959 O algoritmo encontra o caminho mais curto a partir de um nó especifico até todos os outros nós do grafo O algoritmo calcula a maneira mais barata de ir de um nó A a todos os outros nós do grafo GRAFO ALGORITMO DE DIJKSTRA A etiqueta de cada vértice tem as seguinte informações Custo Acumulado CA Vértice Precedente VP Quantidade de Arestas Visitadas QAV Situação do Vértice SV Etiqueta CA VP QAV SV GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Ponto de Partida Vértice 1 Gerar a etiqueta GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 100 1 1 V GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 F Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F Vamos agora gerar as etiquetas do Vertice 5 ligação GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 F Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F Qual tem menor custo Etiquetas do Vertice 5 ligação GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F Vamos agora gerar as etiquetas do Vertice 2 ligações GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F Etiquetas do Vertice 2 ligação Etiqueta CA VP QAV SV 310 2 3 F Etiqueta CA VP QAV SV 550 2 3 F GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 F Etiqueta CA VP QAV SV 310 2 3 F Etiqueta CA VP QAV SV 550 2 3 F Qual tem menor custo Etiquetas do Vertice 2 ligações GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 F Etiqueta CA VP QAV SV 550 2 3 F Qual tem menor custo Etiquetas do Vertice 2 ligações GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 F Vamos agora gerar as etiquetas do Vertice 4 ligação Etiqueta CA VP QAV SV 480 4 3 F GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 F Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 F Etiqueta CA VP QAV SV 480 4 3 F Qual tem menor custo Etiquetas do Vertice 4 ligação GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 F Etiqueta CA VP QAV SV 480 4 3 F Qual tem menor custo Etiquetas do Vertice 4 ligação GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 V Etiqueta CA VP QAV SV 480 4 3 F Qual tem menor custo Etiquetas do Vertice 4 ligação GRAFO ALGORITMO DE DIJKSTRA 100 120 110 90 200 180 330 Etiqueta CA VP QAV SV 0 0 V Etiqueta CA VP QAV SV 220 5 2 V Etiqueta CA VP QAV SV 100 1 1 V Etiqueta CA VP QAV SV 300 5 2 V Etiqueta CA VP QAV SV 310 2 3 V GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Ponto de Partida Vértice 1 Gerar a etiqueta Etiqueta CA VP QAV SV 0 V GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Vamos agora gerar as etiquetas do Vertice 1 ligação Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 F Etiqueta CA VP QAV SV 15 1 1 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Qual tem menor custo Etiquetas do Vertice 1 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Qual tem menor custo Etiquetas do Vertice 1 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Vamos agora gerar as etiquetas do Vertice 4 ligação Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 25 4 2 F Etiqueta CA VP QAV SV 30 4 2 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiquetas do Vertice 4 ligação Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 25 4 2 F Etiqueta CA VP QAV SV 30 4 2 F Qual etiqueta tem menor custo GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 F Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 30 4 2 F Qual tem menor custo Etiquetas do Vertice 4 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 30 4 2 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 20 2 2 F Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 30 4 2 F Vamos agora gerar as etiquetas do Vertice 2 ligação Etiqueta CA VP QAV SV 20 2 2 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 20 2 2 F Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 30 4 2 F Etiquetas do Vertice 2 ligação Etiqueta CA VP QAV SV 20 2 2 F Qual etiqueta tem menor custo GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 20 2 2 F Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 30 4 2 F Etiquetas do Vertice 2 ligação Etiqueta CA VP QAV SV 20 2 2 F Qual etiqueta tem menor custo GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 20 2 2 F Qual tem menor custo Etiquetas do Vertice 2 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 F Etiqueta CA VP QAV SV 20 2 2 F Qual tem menor custo GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F Etiqueta CA VP QAV SV 15 5 3 F Etiquetas do Vertice 5 ligação Qual etiqueta tem menor custo GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F Qual tem menor custo Etiquetas do Vertice 5 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 F Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F Qual tem menor custo Etiquetas do Vertice 5 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 V Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 V Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 F Vamos agora gerar as etiquetas do Vertice 3 ligação GRAFO ALGORITMO DE DIJKSTRA 05 10 15 20 25 05 05 10 10 Etiqueta CA VP QAV SV 0 V Etiqueta CA VP QAV SV 10 1 1 V Etiqueta CA VP QAV SV 5 1 1 V Etiqueta CA VP QAV SV 15 1 1 V Etiqueta CA VP QAV SV 10 4 2 V Etiqueta CA VP QAV SV 20 2 2 V GRAFO REFERÊNCIAS Ascencio Ana Fernanda Gomes Estruturas de dados algoritmos análise da complexidade e implementações em JAVA e CC São Paulo Pearson Prentice Hall 2010 Goodrich Michael T Estruturas de dados e algoritmos em Java recurso eletrônico 5 ed Dados eletrônicos Porto Alegre Bookman 2013 Szwarcfiter Jayme Luiz Estruturas de dados e seus algoritmos 3ed Reimpr Rio de Janeiro LTC 2015 Celes W Cerqueira R Rangel JL Introdução a Estruturas de Dados com Técnicas de Programação em C 2a ed Elsevier ESTRUTURA DE DADOS II Prof Eugênio Júlio Messala Cândido Carvalho eugeniojuliomesslagmailcom 62 992410579 14a ATIVIDADE Grafos ROTAS DE VOOS DOMÉSTICOS Como representar o problema MAPA DE CABOS SUBMARINOS Como representar o problema MAPA DAS ESTRADAS DE GOIÁS Como representar o problema MAPA DAS ESTRADAS DE GOIÁS Como representar o problema REDES SOCIAIS Como representar o problema GRAFO DEFINIÇÃO Um grafo é uma forma de representar relacionamentos que existem entre pares de objetos Isto é um conjunto de objetos chamados de vértices juntamente com uma coleção de conexões entre pares de vértices Um grafo G é simplesmente um conjunto V de vértices e uma coleção E de pares de vértices de V chamados de arestas Assim um grafo é uma forma de representar conexões ou relações entre pares de objetos de algum conjunto V Alguns livros usam uma terminologia diferente para grafos e referemse ao que se chama de vértices como nós e ao que se chama de arestas como arcos GRAFO DEFINIÇÃO Um grafo G é formado pelo par de conjuntos V e E sendo V o conjunto de vértices de G e E o conjunto de arestas de G Uma aresta e EG é representada por e u v e sempre interliga dois vértices quaisquer u e v de V Dois vértices ligados por uma aresta são denominados adjacentes Elementos de um Grafo Vértice Aresta Ligações GRAFO EXEMPLOS Vértice Aresta Grafo não Direcionado Grafo Direcionado Grafo não Direcionado Ponderado Grafo Direcionado Ponderado GRAFO V1 V2 Grafo Não Orientado Um vértice v1 é adjacente a um vértice v2 em G se existe uma aresta conectando v1 a v2 em G Em grafo não orientado v1 é adjacente a v2 se existe aresta v1v2 nesse caso v2 também é adjacente a v1 V1 V2 Grafo Orientado Em grafo orientado v1 é adjacente a v2 se existe aresta v1 v2 GRAFO ORIENTADO Arestas possuem uma direção Alguns autores usam o termo arco para as arestas de um grafo dirigido Exemplo G V E V 1 2 3 4 5 E 1 5 2 3 2 4 3 2 4 3 5 2 5 4 GRAFO NÃO ORIENTADO Arestas são bidirecionais G V E V 1 2 3 4 5 6 E 1 2 1 3 1 4 2 3 2 4 2 6 3 5 4 5 4 6 6 2 GRAFO REPRESENTAÇÃO LISTA DE ADJACÊNCIA DIRIGIDO E PONDERADO 100 120 90 110 200 180 330 Vértices Ponteiro 1 2 3 4 5 Vértice Peso Proximo 5 100 3 90 4 330 2 110 3 180 2 120 4 200 GRAFO REPRESENTAÇÃO LISTA DE ADJACÊNCIA NÃO DIRIGIDO E PONDERADO Vértices Ponteiro 1 2 3 4 5 6 Vértice Peso Proximo 2 10 1 10 3 10 1 15 3 05 4 05 05 10 15 20 25 05 05 10 10 4 20 3 15 4 5 6 10 2 10 5 5 1 5 2 20 5 5 6 25 2 10 4 25 GRAFO PROBLEMA Construir um programa que permita incluir a quantidade de vértices de um grafo qualquer Posteriormente permita incluir excluir e alterar as ligações e pesos entre estes vértices arestas e pesos O programa também deve permitir imprimir as ligações entre os vértices um especifico ou todo o grafo GRAFO REFERÊNCIAS Ascencio Ana Fernanda Gomes Estruturas de dados algoritmos análise da complexidade e implementações em JAVA e CC São Paulo Pearson Prentice Hall 2010 Goodrich Michael T Estruturas de dados e algoritmos em Java recurso eletrônico 5 ed Dados eletrônicos Porto Alegre Bookman 2013 Szwarcfiter Jayme Luiz Estruturas de dados e seus algoritmos 3ed Reimpr Rio de Janeiro LTC 2015 Celes W Cerqueira R Rangel JL Introdução a Estruturas de Dados com Técnicas de Programação em C 2a ed Elsevier ESTRUTURA DE DADOS II Prof Eugênio Júlio Messala Cândido Carvalho eugeniojuliomesslagmailcom 62 992410579 15a ATIVIDADE Grafos ROTAS DE VOOS DOMÉSTICOS Como representar o problema MAPA DE CABOS SUBMARINOS Como representar o problema MAPA DAS ESTRADAS DE GOIÁS Como representar o problema MAPA DAS ESTRADAS DE GOIÁS Como representar o problema REDES SOCIAIS Como representar o problema GRAFO DEFINIÇÃO Um grafo é uma forma de representar relacionamentos que existem entre pares de objetos Isto é um conjunto de objetos chamados de vértices juntamente com uma coleção de conexões entre pares de vértices Um grafo G é simplesmente um conjunto V de vértices e uma coleção E de pares de vértices de V chamados de arestas Assim um grafo é uma forma de representar conexões ou relações entre pares de objetos de algum conjunto V Alguns livros usam uma terminologia diferente para grafos e referemse ao que se chama de vértices como nós e ao que se chama de arestas como arcos GRAFO DEFINIÇÃO Um grafo G é formado pelo par de conjuntos V e E sendo V o conjunto de vértices de G e E o conjunto de arestas de G Uma aresta e EG é representada por e u v e sempre interliga dois vértices quaisquer u e v de V Dois vértices ligados por uma aresta são denominados adjacentes Elementos de um Grafo Vértice Aresta Ligações GRAFO EXEMPLOS Vértice Aresta Grafo não Direcionado Grafo Direcionado Grafo não Direcionado Ponderado Grafo Direcionado Ponderado GRAFO V1 V2 Grafo Não Orientado Um vértice v1 é adjacente a um vértice v2 em G se existe uma aresta conectando v1 a v2 em G Em grafo não orientado v1 é adjacente a v2 se existe aresta v1v2 nesse caso v2 também é adjacente a v1 V1 V2 Grafo Orientado Em grafo orientado v1 é adjacente a v2 se existe aresta v1 v2 GRAFO ORIENTADO Arestas possuem uma direção Alguns autores usam o termo arco para as arestas de um grafo dirigido Exemplo G V E V 1 2 3 4 5 E 1 5 2 3 2 4 3 2 4 3 5 2 5 4 GRAFO NÃO ORIENTADO Arestas são bidirecionais G V E V 1 2 3 4 5 6 E 1 2 1 3 1 4 2 3 2 4 2 6 3 5 4 5 4 6 6 2 Vértices 1 2 3 4 5 1 100 2 90 330 3 110 4 180 5 120 200 GRAFO REPRESENTAÇÃO MATRIZ DE ADJACÊNCIA DIRIGIDO E PONDERADO 100 120 90 110 200 180 330 GRAFO REPRESENTAÇÃO MATRIZ DE ADJACÊNCIA DIRIGIDO E PONDERADO 05 10 15 20 25 05 05 10 10 Vértices 1 2 3 4 5 6 1 10 15 5 2 10 10 20 10 3 15 10 5 4 5 20 5 25 5 5 5 6 10 25 GRAFO PROBLEMA Construir um programa que permita incluir a quantidade de vértices de um grafo qualquer Posteriormente permita incluir excluir e alterar as ligações e pesos entre estes vértices arestas e pesos O programa também deve permitir imprimir as ligações entre os vértices um especifico ou todo o grafo GRAFO REFERÊNCIAS Ascencio Ana Fernanda Gomes Estruturas de dados algoritmos análise da complexidade e implementações em JAVA e CC São Paulo Pearson Prentice Hall 2010 Goodrich Michael T Estruturas de dados e algoritmos em Java recurso eletrônico 5 ed Dados eletrônicos Porto Alegre Bookman 2013 Szwarcfiter Jayme Luiz Estruturas de dados e seus algoritmos 3ed Reimpr Rio de Janeiro LTC 2015 Celes W Cerqueira R Rangel JL Introdução a Estruturas de Dados com Técnicas de Programação em C 2a ed Elsevier