Grafos Ponderados

Um grafo é ponderado quando suas arestas possuem um peso. O que significa isso? Bom… Vamos supor que eu queira ir de um lugar pra outro, mas o mais importante pra mim não seja a distância entre eles mas o pedágio que vou ter que pagar para pegar cada aresta (estrada). Nesse caso, o peso de cada aresta seria o custo que eu tenho pra passar pela estrada. O problema então seria calcular o caminho onde eu pago menos (o caminho que tem a menor soma de preços) e não o menor caminho no grafo “não-ponderado” (onde consideramos aresta=1 e nada=0).

Grafo Ponderado

Neste grafo, por exemplo, o menor caminho de 1 a 3 não é a aresta 1-3, mas sim a aresta 1-2 e depois a aresta 2-3.

Para representar um grafo ponderado usando a matriz de adjacência, onde antes marcávamos “1″, marcamos o peso que temos de ir de um vértice para o outro e onde marcávamos “0″ marcamos [tex]\infty{}[/tex] (infinito)*.

  1 2 3 4
1 [tex]\infty{}[/tex] 10 40 [tex]\infty{}[/tex]
2 10 [tex]\infty{}[/tex] 20 50
3 40 20 [tex]\infty{}[/tex] 20
4 [tex]\infty{}[/tex] 50 20 [tex]\infty{}[/tex]

* Na verdade, só fazemos isso porque neste caso iríamos querer o menor caminho e o 0 poderia atrapalhar, porque poderíamos ter um caminho sem pedágio, por exemplo, mas isso sempre depende do caso.

Usando listas de adjacência, podemos representar as ligações de cada vértice com dois vetores (um para dizer a qual ele se liga e outro o peso desta ligação) ou com um vetor de structs como:

struct edge {
int destino, peso;
};

955 thoughts on “Grafos Ponderados

  1. I used to be more than happy to search out this net-site.I wished to thanks in your time for this excellent learn!! I positively enjoying each little bit of it and I’ve you bookmarked to take a look at new stuff you blog post.

  2. Thank you a lot for providing individuals with such a wonderful opportunity to discover important secrets from here. It is often very kind and as well , stuffed with amusement for me personally and my office friends to visit your blog minimum 3 times weekly to read through the newest stuff you have. And lastly, we are always pleased concerning the magnificent creative concepts served by you. Selected 4 facts on this page are honestly the most beneficial we have had.

  3. Ellanse洢蓮絲(依戀詩)是一款荷蘭與英國共同研發的的新型真皮填充劑,是由30的25-50微米(µm)的聚己內酯(polycaprolactone, PCL)完美微型正圓晶球,以及70的PBS-生物降解材料(carboxymethylcellulose, CMC)製成的凝膠體,這些成分都是通過FDA(美國食品藥品監督管理局)和歐洲CE認證的安全成分,在人體內水分和二氧化碳作用下可以完全被分解吸收和排出的安全物質,對人體不會產生過敏反應,因此治療前不需經過敏檢測,在使用上幾乎不產生副作用。

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>