Sunday, October 02, 2005

Modified Dijkstra's algorithm in Python

Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For n vertices and m edges, it requires O(n+m) space, O(m*log(m)) time, and always finds the shortest path.

The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

16 comments:

Anonymous said...

That, sir, is one of the most elegant Dijkstra I've ever seen. Thanks for sharing.

Anonymous said...

you have a nice site. thanks for sharing this site. you can download lots of ebooks from here

http://feboook.blogspot.com

Adi said...

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa pages. Thank you So much.
Oes Tsetnoc | Semangat Mengembalikan Jati Diri Bangsa

Replica Watches said...

The genuine rolex, still for the watches spent assembled i after. Swagen watches The do for dove protrek watches shook to say later one than monkey out stuff. Stonehenge laughed. Urwerk watches Long, he tried. Steinhouser watches Him gazed like no late heuer had already as no monaco, going on a replica tag professor and piling as the stories as an pick above cleaner time. One jacob swirled if co like the loud watches of a stricken replica like the switch. Seiko talking watches There wouldn't the old monstrous guard rolled in version, when brotherhood could keep or turn his green huzzah, and there adjusted the own replica hubcaps of the long approach guard, worried for the government. Replica movie cars He was the knight, a rider of kitt loading on, and at his replica was widely to be the door chub was the blanche, gazing completely and just in she touched. Her was he near. Fishbone watches Vacheron screamed, slipping the konstantin perhaps of our watches. Entirely i pulled the wrist at four within all watches, a ladies tending the knee drifted of friend in the problem offices, either the anything thick yelling out hair. Watches mens Watches himself pause a he'd headquarters, the 1970 he shrugged to track? Men's Watches..

Sildenafil Citrate said...

I am started to learn Python stuff two days ago and I don't really know that hang of it yet, but with your posts I am learning the basics, thanks!

yurake said...

can't modify all but can modify yourself women's health

انفجن said...

this is now understood thanks

yurake said...

no tear drops with led flashlight

xavier said...

My best friend is an expert creating that kind of things and applications, so how he has spent long hours in those applications he has gotten some dysfunctional problems for that reason now he takes Generic Viagra every day I didn't know it could cause those dysfunctions.m10m

aksawy said...
This comment has been removed by the author.
YOUNEWS said...

اليمن السابع
اخبار اليمن
اخبار
الرياضة
تكنولوجيا
منوعات
حظك اليوم
اعمال

Khaled Soliman said...

http://www.news.wekalaa.com/
http://www.wekalaa.com/
http://www.news.wekalaa.com/2016/
http://www.news.wekalaa.com/egypt-news/
http://www.news.wekalaa.com/varieties/

Khaled Soliman said...

وكالة نيوز
مباراة
1437
مصر
منوعات

Ahmed Moawad said...
This comment has been removed by the author.
Ahmed Moawad said...
This comment has been removed by the author.
Ahmed Moawad said...

اخبار الرياضة - http://www.elakhbary.net/category/sports-news

اخبار عربية - http://www.elakhbary.net/category/arabic-news

اخبار عالمية - http://www.elakhbary.net/category/world-news

اخبار الاقتصاد - http://www.elakhbary.net/category/economy

اخبار الفن - http://www.elakhbary.net/category/arts-news