Solved

Dijkistra Shortest Path

Posted on 1997-07-22
3
774 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

Industry Leaders: 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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

734 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