30:T601,function dijkstra(digrafo, origem, destino = null) { // Estrutura de dados representando árvore de menores caminhos let infoVertice = new Map(); infoVertice.set (origem, {distancia:0, predecessor: null}) // Conjunto de vértices a visitar let avisitar = new Set(); avisitar.add (origem); while (avisitar.size > 0) { // Buscar vertice com menor distância entre os ainda não visitados let melhorVertice = null; let menorDistancia = Number.POSITIVE_INFINITY; for (let v of avisitar) { let info = infoVertice.get(v); if (info.distancia < menorDistancia) { melhorVertice = v; menorDistancia = info.distancia; } } // Terminar se o vertice destino foi encontrado if (melhorVertice == destino) break; // Não visitar mais este vértice avisitar.delete(melhorVertice); // Testar vizinhos e atualizar estrutura de dados for (let vizinho of digrafo.verticesAdjacentes(melhorVertice)) { let dist = menorDistancia + digrafo.peso (melhorVertice, vizinho); if (infoVertice.has(vizinho)) { // Vértice já alcançado por algum caminho let info = infoVertice.get(vizinho); if (dist < info.distancia) { info.distancia = dist; info.predecessor = melhorVertice; } } else { // Vértice ainda não alcançado infoVertice.set(vizinho, {distancia:dist, predecessor: melhorVertice}); avisitar.add (vizinho) } } } return infoVertice }31:T585,function dijkstraRapido(digrafo, origem, destino = null) { // Fila de prioridades let fila = new PriorityQueue (); // Estrutura de dados representando árvore de menores caminhos let infoVertice = new Map(); let no = fila.insert (0, origem); infoVertice.set (origem, {no: no, distancia:0, predecessor: null}) while (!fila.isEmpty()) { // Obter vertice com menor distância entre os ainda não visitados let no = fila.extractMinimum(); let melhorVertice = no.value; let menorDistancia = no.key; // Terminar se o vertice destino foi encontrado if (melhorVertice == destino) break; // Testar vizinhos e atualizar estrutura de dados for (let vizinho of digrafo.verticesAdjacentes(melhorVertice)) { let dist = menorDistancia + digrafo.peso (melhorVertice, vizinho); if (infoVertice.has(vizinho)) { // Vértice já alcançado por algum caminho let info = infoVertice.get(vizinho); if (dist < info.distancia) { info.distancia = dist; info.predecessor = melhorVertice; fila.decreaseKey(info.no, dist); // Atualizar fila de prioridades } } else { // Vértice ainda não alcançado let noVizinho = fila.insert(dist,vizinho); infoVertice.set(vizinho, {no: noVizinho, distancia:dist, predecessor: melhorVertice}); } } } return infoVertice }32:T703,function prim(digrafo,raiz) { // Computar vértices a conectar let aconectar = new Set() for (let u of digrafo.vertices()) aconectar.add(u) // Inicializar mst, o resultado do algoritmo let mst = new Digrafo(); mst.adicionarVertice(raiz); aconectar.delete(raiz); // Estrutura que associa vértices conectados aos não conectados mais próximos let candidatos = new Map(); // Função que atualiza candidatos com a aresta de menor custo ligando // um vértice ainda não conectado a u let atualizaCandidatos = function (u) { let menor_distancia = Number.POSITIVE_INFINITY; let mais_proximo = null; for (let v of digrafo.verticesAdjacentes(u)) { if (aconectar.has(v) && digrafo.peso(u,v) < menor_distancia) { menor_distancia = digrafo.peso(u,v) mais_proximo = v } } if (mais_proximo) candidatos.set(u,mais_proximo); else candidatos.delete(u) } atualizaCandidatos (raiz); // Repetidamente acrescentar na mst a aresta de menor custo ligando um // vertice ainda não conectado com algum já na mst while (aconectar.size > 0) { // Achar melhor aresta let [melhor_u, melhor_v, menor_distancia] = [null, null, Number.POSITIVE_INFINITY]; for (let [u,v] of candidatos.entries()) { if (v && digrafo.peso(u,v) < menor_distancia) { [melhor_u, melhor_v, menor_distancia] = [u,v,digrafo.peso(u,v)] } } // Se grafo não é conexo, pode não haver candidato viável if (menor_distancia == Number.POSITIVE_INFINITY) break; // Atualizar mst.adicionarVertice(melhor_v); mst.conectarVerticesDir(melhor_u, melhor_v, menor_distancia); aconectar.delete(melhor_v) atualizaCandidatos(melhor_u); atualizaCandidatos(melhor_v); } return mst }33:[] 2e:{"title":"Grafos - Capítulo 7","cells":[{"id":0,"value":"md`# Grafos - Capítulo 7\n\nEste caderno de notas contém código adaptado do livro sobre grafos de João Paulo Maida. Procurei adaptar as classes e construções do livro para a linguagem JavaScript de forma a facilitar a expressão dos algoritmos e estruturas de dados.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"md`## Classe \\`Digrafo\\` (capítulo 6)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"import { Digrafo, digrafo } from \"@esperanc/grafos-capitulo-6\" ","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"md`## Dijkstra simples sem fila de prioridades\n\nRetorna uma estrutura de dados representando uma \nárvore com todos os menores caminhos a partir do vértice \\`origem\\`. Se \\`destino\\` for especificado, \nconstrói a estrutura somente até encontrar o vértice \\`destino\\`.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":124,"value":"md`## Dijkstra mais eficiente usando fila de prioridades\n\nAlgoritmo análogo ao simples, mas usando uma fila de prioridades para armazenar os vértices em ordem de distância até o vértice \\`origem\\`. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":108,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"md`## Exemplo: menor caminho entre duas cidades usando Dijkstra`","pinned":false,"hidden":false,"mode":"ojs"},{"id":66,"value":"viewof origem = select({title:\"Vértice origem\", options:Array.from(digrafo.vertices()), value:\"RJ\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"viewof destino = select({title:\"Vértice destino\", options:Array.from(digrafo.vertices()), value:\"CR\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":119,"value":"viewof algoritmo = radio({title:\"Versão do algoritmo de Dijkstra\", options:[\"Simples\",\"Rápido\"], value:\"Simples\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"infoVertice = (algoritmo == \"Simples\" ? dijkstra : dijkstraRapido) (digrafo,origem)","pinned":true,"hidden":false,"mode":"ojs"},{"id":233,"value":"caminhoDijkstra = {\n let vertice = destino;\n let caminho = [destino];\n while (vertice != origem) {\n let info = infoVertice.get(vertice);\n if (!info) break; // Vértice não alcançado\n vertice = info.predecessor;\n caminho.push (vertice)\n }\n caminho.reverse()\n return caminho\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":28,"value":"{\n let gv = digrafo.graphViz(true);\n let vertice = destino;\n // Marcar no desenho o caminho até origem em vermelho\n while (vertice != origem) {\n let info = infoVertice.get(vertice);\n if (!info) break; // Vértice não alcançado\n let aresta = info.predecessor+\" -> \"+vertice+\"[\";\n gv = gv.replace (aresta,aresta+'color=\"red\",');\n vertice = info.predecessor\n }\n return dot`${gv}`\n} ","pinned":true,"hidden":false,"mode":"ojs"},{"id":243,"value":"md`## Algoritmo de Floyd-Warshall\n\nDado um dígrafo, retorna uma matriz com tantas linhas e colunas quanto os vértices. Um elemento (*u*, *v*), correspondente à linha *u* coluna *v*, contém duas informações: a menor distância (comprimento do caminho) entre *u* e *v* e qual o próximo vértice a ser visitado a partir de *u* no caminho que leva a *v*. Desta forma, a matriz codifica todos os caminhos mínimos entre todos os pares de vértices do dígrafo.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"function floyd(digrafo) {\n \n // Inicializar matriz de distâncias \n let matriz = new Map()\n for (let u of digrafo.vertices()) {\n let linha = new Map();\n matriz.set(u, linha);\n for (let v of digrafo.vertices()) {\n linha.set(v, {proximo : v, \n distancia: u == v ? 0 : digrafo.peso(u,v) || Number.POSITIVE_INFINITY})\n }\n }\n \n // Preencher matriz considerando caminhos com cada vez mais intermediários \n for (let k of digrafo.vertices()) {\n let linha_k = matriz.get(k)\n for (let u of digrafo.vertices()) {\n let linha_u = matriz.get(u);\n let uk = linha_u.get(k);\n for (let v of digrafo.vertices()) {\n let kv = linha_k.get(v);\n if (uk.distancia + kv.distancia < linha_u.get(v).distancia) {\n linha_u.set(v, { proximo : uk.proximo, distancia : uk.distancia+kv.distancia })\n }\n }\n }\n }\n return matriz\n}\n ","pinned":true,"hidden":false,"mode":"ojs"},{"id":272,"value":"md`## Exemplo: matriz de menores caminhos usando algoritmo de Floyd-Warshall`","pinned":false,"hidden":false,"mode":"ojs"},{"id":255,"value":"matrizDistancia = floyd(digrafo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":303,"value":"{\n let s = \"style='border:1px solid black; text-align:center'\";\n let table = html`

`;\n let row = html``; table.append(row);\n for (let u of matrizDistancia.keys()) row.append(html`${u}`);\n for (let [u,linha] of matrizDistancia.entries()) {\n let row = html`${u}`; table.append(row);\n for (let [v,elemento] of linha.entries()) {\n let {proximo,distancia} = elemento;\n if (distancia == Number.POSITIVE_INFINITY) \n row.append(html`(∞)`)\n else\n row.append(html`${proximo} (${distancia})`)\n }\n }\n return table\n}\n ","pinned":false,"hidden":false,"mode":"ojs"},{"id":323,"value":"md`## Exemplo: reconstrução do menor caminho\n\nComputa o menor caminho entre um vértice origem e um vértice destino dados usando a matriz de distâncias computada pelo algoritmo de Floyd-Warshall.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":276,"value":"viewof origemFloyd = select({title:\"Vértice origem\", options:Array.from(digrafo.vertices()), value:\"RJ\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":278,"value":"viewof destinoFloyd = select({title:\"Vértice destino\", options:Array.from(digrafo.vertices()), value:\"CR\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":294,"value":"caminhoFloyd = {\n let vertice = origemFloyd;\n let caminho = [origemFloyd];\n while (vertice != destinoFloyd) {\n let elemento = matrizDistancia.get(vertice).get(destinoFloyd);\n if (!elemento || elemento.distancia == Number.POSITIVE_INFINITY) break; // Vértice não alcançado\n vertice = elemento.proximo;\n caminho.push (vertice)\n }\n return caminho\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":280,"value":"{ \n let gv = digrafo.graphViz(true);\n let vertice = origemFloyd;\n // Marcar no desenho o caminho até origem em vermelho\n while (vertice != destinoFloyd) {\n let elemento = matrizDistancia.get(vertice).get(destinoFloyd);\n if (elemento.distancia == Number.POSITIVE_INFINITY) break; // Vértice não alcançado\n let aresta = vertice +\" -> \"+elemento.proximo+\"[\";\n gv = gv.replace (aresta,aresta+'color=\"red\",');\n vertice = elemento.proximo\n }\n return dot`${gv}`\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":318,"value":"md`## Algoritmo de Prim\n\nDado um vértice raiz e um dígrafo, encontra um subgrafo que é uma *árvore geradora mínima* da componente conexa do dígrafo que contém o vértice raiz.` ","pinned":false,"hidden":false,"mode":"ojs"},{"id":332,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":348,"value":"md`## Exemplo de árvore geradora mínima usando Prim`","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"viewof raizPrim = select({title:\"Vértice raiz\", options:Array.from(digrafo.vertices()), value:\"RJ\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":337,"value":"dot`${prim(digrafo,raizPrim).graphViz(true)}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":18,"value":"md`## Bibliotecas`","pinned":false,"hidden":false,"mode":"ojs"},{"id":84,"value":"md`**graphviz** (para desenho de grafos)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"dot = require(\"@observablehq/graphviz@0.2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":88,"value":"md`**inputs** (para elementos de interface gráfica)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":62,"value":"import { radio, select } from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":93,"value":"md`**Fibonacci heap** (implementação de fila de prioridades)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"FibonacciHeapModule = require('https://bundle.run/@tyriar/fibonacci-heap@2.0.9')","pinned":true,"hidden":false,"mode":"ojs"},{"id":104,"value":"PriorityQueue = FibonacciHeapModule.FibonacciHeap","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}