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;
};

2,821 thoughts on “Grafos Ponderados

  1. Great Information for the naive public that has been taught that psychiatrist are knowledgeable, skilled and compassionate people helping our society’s forgotten. It is great that they are being exposed for the criminals that hurt in the name of help.

  2. I wanted to write a small note to be able to appreciate you for those fantastic concepts you are posting at this site. My extensive internet search has at the end been compensated with reliable facts and strategies to go over with my neighbours. I ‘d state that that many of us website visitors actually are truly fortunate to be in a good community with many outstanding people with interesting opinions. I feel somewhat fortunate to have encountered your entire weblog and look forward to some more thrilling moments reading here. Thanks a lot again for a lot of things.

  3. Thank you so much for providing individuals with remarkably superb chance to check tips from this web site. It is usually very awesome and also full of a lot of fun for me personally and my office friends to visit your website no less than three times in a week to see the newest tips you have. Not to mention, I’m so at all times motivated with the special techniques served by you. Certain 4 ideas on this page are honestly the most efficient we have all ever had.

  4. Heu le plus con dans le raisonnement "avec un miroir ça passe" c'est que, avec un détecteur à laser ce qui déclenche l'alarme c'est pas qu'on touche le laser mais qu'il n'arrive pas à son point d'arrivéschéma:arrivé départ[———————–<|rien ne se passe…arrivé miroir départ[ \\———–<|pin pon pin pon v'la les polisson !voili voilou

  5. भुत = बहुत.क्षमा कीजिये मेरे कीपेड की अ की जरा परेशां करती है :०

  6. Läste i GP idag att det hittats Tussilago i Sthm. Vårblommor finns tydligen även på Öland. Kan jag inbilla mig att det snart är vår? (Tyvärr läste även en annan notis i Gp, att det är snö på väg, dock hoppas jag att det faller ner som regn istället)

  7. Sorry but I wasn't thinking about that asshole Ezra tonight. This evening it's about the U.S.A. and the American people and how to introduce them to how power is held in their country and how it ought to be held.I just cant bring myself to care in the slightest about Ezra. He's a bit of a jumped up idiot.

  8. Thanks for your publication. What I want to comment on is that when you are evaluating a good on the internet electronics retail outlet, look for a site with full information on important factors such as the level of privacy statement, safety details, any payment guidelines, and other terms in addition to policies. Continually take time to see the help and also FAQ segments to get a greater idea of the way the shop will work, what they are capable of doing for you, and ways in which you can make the most of the features.

  9. Pues será que otros seres de otros universos ó dimensiones se intentan colar en nuestro mundo, viajando a través del tiempo con esos agujeros de gusano.O quizá sean consecuencia de ese aparato monstruoso LHC del Cern en Suiza que quiere regenerar el BigBang y se generan microagujeros negros que por fortuna se evaporan porque si no se traga a nosotros y el resto del Sistema Solar.

  10. I precisely desired to thank you very much again. I’m not certain the things I would have done without the techniques shared by you directly on such question. It became an absolute hard matter in my circumstances, however , viewing your skilled technique you handled the issue took me to weep for gladness. I’m just happier for the assistance and in addition wish you comprehend what an amazing job you were accomplishing teaching others via your blog post. I’m certain you’ve never encountered all of us.

  11. Wprawdzie dereniowki robic nie bede,ale wyobraz sobie,ze kilka dereni mi rosnie praktycznie pod balkonem i juz robilam z nich dzemik-haaa…..pamietalam z zeszlego roku moja niepewnosc,co do niego i jednak sie okazalo,ze to naprawde deren :) z dala od ulicy i aut…mysle,ze sie nadaje :) Ciasto wspaniale zrobilas,lubie takie proste tarty :) Usciski Basiu :)

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>