Aula 7

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

7 - Grafos e multicaminhos
	
7.1 - Representação de multicaminhos por grafos
	
	Um digrafo é considerado como sendo fortemente conectado quando todos os seus vértices podem ser alcançados por um caminho, não importando o vértice inicial utilizado; ou seja, existe pelo menos um caminho formado por arestas direcionadas que conecta quaisquer dois vértices do grafo.
	
	Quando um caminho de um grafo forma um ciclo (partindo de um vértice, é possivel voltar a esse mesmo vértice), esse caminho é denominado "ciclo dirigido".
7.2 - Algoritmo de Dijkstra para determinar caminhos
	
	A busca sistematica em grafos não ponderados para encontrar todos os vértices alcançaveis a partir de um vértice inicial pode ser realizada por dois métodos básicos:
	• Pesquisa em profundidade
	• A pesquisa em largura é particularmente util para determinar o caminho mais curto entre dois vértices, entretando, nesse método, o caminho é medido pela quantidade de arestas entre os vértices, sem considerar o tamanho (ou peso) de cada aresta.
	
	O algoritmo publicado por Dijkstra, utiliza a representação baseada em matriz de adjancencia de um grafo ponderado e permite encontrar o caminho mais curto entre um vértice inicialmente selecionado e todos os demais vértices alcançaveis a partir desse vértice inicial. O algoritmo retorna o peso total do menor caminho entre os dois vértices, ou seja, a soma dos pesos de todas as arestas que formam o menor caminho.