15,968,214 members
1.00/5 (1 vote)
See more:
hi i am really confuse how to find shortest path this code shows the minimum distance but not path kindly explain me.
thank you

here is link of the code.

Posted

Solution 1

There are lots of articles on this very page, see if you cant find the answer here:
Dijstra algorithm[^]

Solution 2

Hey!

I wroted the dijgstra 2 days ago.
If you want look this code:

C++
```#include <cstdio>
#define MAXN 150
#define MAX_VALUE 10000
#define NO_PARENT (unsigned)(-1)
const unsigned S = 1;
const unsigned N = 10;

unsigned Matrix[MAXN][MAXN] =
{
{0, 23, 0, 0, 0, 0, 0, 8, 0, 0},
{23, 0, 0, 3, 0, 0, 34, 0, 0, 0},
{0, 0, 0, 6, 0, 0, 0, 25, 0, 7},
{0, 3, 6, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 10, 0, 0, 0, 0},
{0, 0, 0, 0, 10, 0, 0, 0, 0, 0},
{0, 34, 0, 0, 0, 0, 0, 0, 0, 0},
{8, 0, 25, 0, 0, 0, 0, 0, 0, 30},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 7, 0, 0, 0, 0, 30, 0, 0},
};

char Tops[MAXN];
unsigned d[MAXN];
int pred[MAXN];

void Dijkstra(unsigned s)
{
unsigned i;
for(i = 0; i < N; i++)
{
if(Matrix[s][i] == 0)
{
d[i] = MAX_VALUE;
pred[i] = NO_PARENT;
}
else
{
d[i] = Matrix[s][i];
pred[i] = s;
}
}
for(i = 0; i < N; i++)Tops[i] = 1;
Tops[s] = 0;
while(true)
{
unsigned j = NO_PARENT;
unsigned di = MAX_VALUE;

for(i = 0; i < N; i++)
{
if(Tops[i] && d[i] < di)
{
di = d[i];
j = i;
}
}

if(NO_PARENT == j)break;
Tops[j] = 0;
for(i = 0; i < N; i++)
{
if(Matrix[j][i] != 0 && Tops[i])
{
if(d[i] > d[j] + Matrix[j][i])
{
d[i] = d[j] + Matrix[j][i];
pred[i] = j;
}
}
}
}
}

void printPath(unsigned s, unsigned j)
{
if(pred[j] != s)printPath(s, pred[j]);
printf(" %u", j + 1);
}

void printResult(unsigned s)
{
unsigned i;
for(i = 0; i < N; i++)
{
if(i != s)
{
if(d[i] == MAX_VALUE)
{
printf("NO PATH FROM TOP %u TO TOP %u\n", s + 1, i + 1);
}
else
{
printf("MINIMAL PATH FROM TOP %u TO TOP %u: %u", s + 1, i + 1, s + 1);
printPath(s, i);
printf(", PATH LEINTH: %u\n", d[i]);
}
}
}
}

int main()
{
Dijkstra(S - 1);
printResult(S - 1);
return 0;
}</cstdio>```

:)