944,004 Members | Top Members by Rank

Ad:
Dec 2nd, 2006
0

Dijkstra's alogirthm & Shortest path problems

Expand Post »
Hi,
I am having trouble to find the specific information about Dijkstra agorithm and Shortest Path techniques for my following two problems. Please help me by providing either specific answer or URL for my questions. I appreciate your help.
==============================
[1] What is the running time of Dijkstra’s algorithm if the min-priority queue is implemented using a sorted array. I need to prove the answer by giving an example.

[2] Dijkstra’s algorithm can be easily modified to work on undirected graphs. Let T be a tree of shortest paths constructed by the modified algorithm for an undirected, connected, weighted graph G with positive weights.
1. True or false: T is a spanning tree of G? If it is true, give a proof. If it is false, give a counterexample.
2. True or false: T is a minimum spanning tree of G? If it is true, give a proof. If it is false, give a counterexample.
=====================================
Thanks in advacne for all input.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Shailesh33 is offline Offline
4 posts
since Sep 2006
Dec 2nd, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

The point of the questions is for you to do the analysis and come up with an answer. Any loser can find the answer by exhaustively searching for it online (well, maybe not any loser ); a promising computer scientist, as I'm sure you are, isn't afraid to figure it out for himself.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Dec 2nd, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

[search]dijkstra's algorithm[/search]

You gotta love our new search bbcode
Administrator
Staff Writer
Reputation Points: 1422
Solved Threads: 162
The Queen of DaniWeb
cscgal is offline Offline
13,645 posts
since Feb 2002
Dec 2nd, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

>You gotta love our new search bbcode
It's a whole new level of catering to lazy people.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Dec 2nd, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

Don't worry - I'll have you using it in no time
Administrator
Staff Writer
Reputation Points: 1422
Solved Threads: 162
The Queen of DaniWeb
cscgal is offline Offline
13,645 posts
since Feb 2002
Dec 5th, 2006
-1

Re: Dijkstra's alogirthm & Shortest path problems

I found no help from this Forum...it is westing of time..
People know how to give advice but don't know how to answer...
-sorry
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Shailesh33 is offline Offline
4 posts
since Sep 2006
Dec 5th, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

>I found no help from this Forum...it is westing of time..
The feeling is mutual. After seeing how grateful you are that I saved you from making a huge mistake by not learning anything, I feel like I've wasted my time.

>People know how to give advice but don't know how to answer...
Here's an answer: Do your own homework! I've already done this stuff for myself, so why should I do it for you? What if you sail through your coarses and then become my co-worker? Then I have to deal with your incompetence because I did your work for you. Sorry, but I'm on a quest to improve the field, and people like you just drag it further into the gutter.
Administrator
Reputation Points: 6442
Solved Threads: 1393
Bad Cop
Narue is offline Offline
11,807 posts
since Sep 2004
Dec 5th, 2006
0

Re: Dijkstra's alogirthm & Shortest path problems

Click to Expand / Collapse  Quote originally posted by Shailesh33 ...
I found no help from this Forum...it is westing of time..
People know how to give advice but don't know how to answer...
-sorry
You have to remember that this is a community of volunteers. No one is here because they have to be. They are here because they want to be. Every time a member here assists someone in any way it is a gesture of kindness and selflessness. You should never expect expect someone to give you what you are looking for. You can hope and you should ask for help, but never expect things to be handed to you. Especially when it is obvious that you are expecting them to do your homework for you. We want to help you learn but not by doing your work for you.

You should also be grateful for any response you get. Being negative, like you have here, only serves to prevent members from helping you any further in this thread and in the future. That's certainly not what you are after.

Hopefully you remember this so in your future endevours on this forum, or any other forum, you might behave in a more positive and professional manner and get the help it is you seek.
Moderator
Reputation Points: 161
Solved Threads: 38
He's No Good To Me Dead
stymiee is offline Offline
1,422 posts
since May 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
This thread is currently closed and is not accepting any new replies.
Previous Thread in Computer Science Forum Timeline: The difference between Big-oh and theta notation
Next Thread in Computer Science Forum Timeline: Artificial Intelligence





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC