Dijkstra's Algorithm

[gopunk]

Originally posted by: IcemanJer
Oh wait, you just have to explain how Dijkstra works, and not actually prove it?

yea... the assignment is to explain how it works (not why it works, i assume). i wanted to see if there was a simple direct proof, just for my own curiosity.

 

[abaez]

Originally posted by: Dead Parrot Sketch
All I remember is it has something to do with Refrigerator Perry.

LMAO

 

[hudster]

Edsger Wybe Dijkstra: 1930-2002

here's hoping that he found the shortest path to a better place from here.


I especially enjoy this tidbit:
"He and his wife had a fondness for exploring state and national parks in their Volkswagen bus, dubbed the Touring Machine"

ahh, a geek with a sense of humor is a scary thing.

R.I.P. Mr. Dijkstra

 

[Orsorum]

Originally posted by: gopunk

Originally posted by: Zakath15

Originally posted by: gopunk

Originally posted by: Zakath15
Do you use TeX?

yup

miktex + winedt =

What a coincidence... I'm using that for my Econ 400 hw right now.

*twilight zone music*

Creeeeeepy...:Q *looks around nervously*

 

[IcemanJer]

Originally posted by: gopunk
yea... the assignment is to explain how it works (not why it works, i assume). i wanted to see if there was a simple direct proof, just for my own curiosity.

Ah, gotcha.. yeah, as far as I know it's always been proved using contradiction. I mean, it's easy and straight-forward to prove it by contradiction.. and to prove Dijkstra's by direct proof, you'd have to prove the "for all..." thing instead of just proving one false case.

 

[schizoid]

Originally posted by: gopunk

Originally posted by: BatmanNate
Proof

*cough* that's a proof by contradiction....

also it doesn't really explain why it works... just that it is impossible for it not to.

Well, I don't think what you said there makes any sense.

Why does it work? Because if it didn't, that would mean our system of math didn't work. If we were to assume that our system of math does work, then the algo works.

Happy fun times.

But didn't he play for the Mets and the Phillies? And like, he always was spitting tobacco?

Anyways, yeah.


<=== monkey dance

LOL your face!

 

[KEV1N]

What's wrong with proof by contradiction? ~Q -> P <=> P -> Q !!!

 

[JEDI]

Originally posted by: IcemanJer

Originally posted by: gopunk
bump for v2.0

what do you guys think of my explanation? any suggestions?

mm... it's kinda weak IMHO... you might want to mention the optimal substructure property of shortest paths.

Dijkstra's algorithm is most easily proved by contradiction, and if you want to do a direct proof it's gonna be long and ugly. And the running time o Dijkstra is actually more like Theta(v lg v + e), where v = number of nodes, e = number of edges.

um..what he said