Showing results for

- Intel Community
- FPGAs and Programmable Solutions
- Nios® II Embedded Design Suite (EDS)
- Shortest Path Between Two Points

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-29-2013
03:38 AM

716 Views

Shortest Path Between Two Points

Hi folks,

Please consider the following code:```
# include <limits.h># include <stdio.h># include <stdlib.h>
# define INFINITY INT_MAX# define MAXNODES 12# define MEMBER 1# define NONMEMBER 0
void shortpath(w, s, t, pd, precede)
int w;
int s, t, *pd, precede;
{
int distance, perm;
int current, i, k, dc;
int smalldist, newdist;
/* initialization */
for (i = 0; i < MAXNODES; ++i){
perm = NONMEMBER;
distance = INFINITY;
}
perm = MEMBER;
distance = 0;
current = s;
while (current != t){
smalldist = INFINITY;
dc = distance;
for (i = 0; i < MAXNODES; i++)
if (perm == NONMEMBER){
newdist = dc + w;
if(newdist < distance){
/* distance from a to i through current is less than distance */
distance = newdist;
precede = current;
}
/* short distance assignment */
if (distance < smalldist) {
smalldist = distance;
k = i;
}
}
current = k;
perm = MEMBER;
}
*pd = distance;
}
int main()
{
int w, i, j;
int pd, s, t;
int precede;
for(i=0; i<MAXNODES; i++){
for(j=0; j<MAXNODES; j++){
w = INFINITY;
}
}
for(i = 0; i < MAXNODES; i++){
for(j=0; j<MAXNODES; j++){
if(i == j) w = 0;
}
}
w = 7;
w = 9;
w = 14;
w = 10;
w = 15;
w = 11;
w = 2;
w = 6;
w = 9;
for(i = 0; i < MAXNODES; i++){
for(j=0; j<MAXNODES; j++){
if(i > j) w = w;
}
}
/* checking if adjacency matrix is ok */
for(i = 0; i < 6; i++){
for(j=0; j<6; j++){
if(w > 1000) printf("M\t");
else printf("%d\t", w);
}
printf("\n");
}
printf("Enter s-->");
scanf("%d", &s);
while(s != -1){
printf("Enter t-->");
scanf("%d", &t);
shortpath(w, s, t, &pd, precede);
printf("Shortest distance between %d and %d --> %d\n", s, t, pd);
fflush(stdin);
printf("Enter s-->");
scanf("%d", &s);
}
system("PAUSE");
return(EXIT_SUCCESS);
}
```

It is expected for this code process the shortest distance between node "s" and node "t", given an adjaceny matrix "w" (containing weights between the nodes). Non-adjacency nodes are linked by an INFINITY weight. The function used return the distance in the "pd" variable. In a first test, only considering imediate adjacent nodes, this code is only working for the expected distances between (1,0), (3,4) and (5,2). The remaining adjacent distances, e.g., (0,2), (1,2), (3,1), etc, are giving an infinite distance. Two questions: 1) Is it ok posting generalized C questions here? 2) If 'yes' to the previous answer, what is wrong and what is the fix? Regards Jaraqui
2 Replies

Highlighted
##

*; *

* *

*with: *

*if(w[current]* != INFINITY) { newdist = dc + w[current][i]; } else { newdist = INFINITY; } I think you end up adding a positive number to INFINITY which gives you a large negative that incorrectly satisfies your check for "less than".

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-30-2013
10:09 PM

3 Views

1) Ask anything you like, no guarantee it will get answered.

2) If you haven't fixed this already, I suggest you replace: this: newdist = dc + w[current]
Highlighted
##

Altera_Forum

Valued Contributor III

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

11-04-2013
07:50 PM

3 Views

Hi ghogerheiden,

I fixed the code, but I don´t remember exactly what was the fix. But thank you very much for your cooperation! best regards JaraquiFor more complete information about compiler optimizations, see our Optimization Notice.