Solved

Dijkistra Shortest Path

Posted on 1997-07-22
3
771 Views
Last Modified: 2006-11-17
Hi guys
Does anyone has the source for Dijkistra's 'Shortest Path' algorithm?
0
Comment
Question by:kkarnez
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 5

Expert Comment

by:julio011597
ID: 1252504
Finding the Shortest Path in a dense graph??

I'll post it if you swear this is not a homework ;)

-julio
0
 

Author Comment

by:kkarnez
ID: 1252505
Of course...
0
 
LVL 4

Accepted Solution

by:
emmons earned 100 total points
ID: 1252506
From "design and analysis of algorithms" - Jeff Smith

/* given a set of n vertices, a source vertex v and an nx n cost array c, this algorithm returns the cost fo the cheapest path from v to every other vertex. The vertices are index from 1 to n: T[i] is true iff the vertex i is included in T */
SingleSource( n,v,c)
for( i=1 to n) {
cost[i] = c[v,i]; /* initialise cost matrix */
T[v] = false; /* T is initially empty */
}
T[v] = true; /* include source vertex in T */
newest = v; /* newest node used to update cost */
for( i = 2 to n) { /* choose the ith vertex of T and see */
leastcost = INFINITY /* if inclusion of the latest */
for( j=1 to n) { /* node in T allows cheaper access */
if( !T[j] ) { /* to any node not in T */
if( cost[newest] + c[newest,j] < cost[j]) {
cost[j] = cost[newest] + c[newest,j];
} /* endif */ /* kind of useless if i = 2 */
if( cost[j] < leastcost) { /*and keep track of */
cheapest = j; /* the vertex not in T */
leascost = cost[j]; /* with the lowest access */
} /* endif */
} /* endif *
T[cheapest] = true; /* include this vertex in T */
newest = cheapest /* and record it as the */
} /* end for */ /* newest vertex */
} /* end for */
return (cost);
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

732 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question