Estudo de Árvore Geradora Mínima com uma modelagem do Algoritma de Prim em VBA

Dentre os principais problemas de otimização em rede está a obtenção de árvores geradoras mínimas. Dado um grafo ponderado e não direcionado, cujos pesos representam o custo associado a cada aresta, deseja-se encontrar um subgrafo acíclico que contém todos os vértices do grafo original e minimiza o somatório dos custos de modo que as arestas selecionadas conectem todos os nós entre si, havendo sempre um caminho simples de um ná a qualquer outro. O problema retrata várias situações reais, tais como: projeto de rede de telecomunicações com o mínimo custo, projeto de rede de dutos subterrâneos, projeto de uma rede de linhas de transmissão, etc. Dentre as técnicas clássicas usadas para a resolução desses problemas, está o algoritmo de Prim. Este estudo apresenta uma modelagem em VBA para o método e sua aplicação em uma instância do problema discutida previamente na literatura, consistindo na busca da árvore geradora mínima para uma rede óptica de telecomunicações na Itália. Os resultados ilustram a resolução da instância por meio do programa, incluindo as telas expostas para o usuário e as visualizações geradas pelo programa para a árvore geradora encontrada.