How to print the Dijkstra SSSP in order in C?-CodePudding

I have a working code that prints the SSSP from destination to source, but I want it to be in reverse i.e. source to destination.

I can't figure out how to do this. The loop I currently use to print the path is this:

for(i = 1; i <= T->vertices; i  ){
    if(T->parent[i] != -1){
      printf("SSSP Distance from %d->%d is %d: {%d", T->visited[i],i,T->distance[i],i);

      j = i;
      while(T->parent[j] != -1){ //the path is printed backwards, but still in order.
        j = T->parent[j];
        printf("<-%d", j);
      }
      printf("}\n");
    }   
  }

Let's say that this generates a path of 3<-4<-1 and another that is 2<-1, where 3 is the destination and 1 is the source/starting node.

I want it to print 1->4->3 and 1->2 instead.

CodePudding user response：

You can consider using the stack to store the traversal results first, and then outputting the contents of the stack should give you the result you want.

CodePudding user response：

Use a recursive path printer. You have:

for (i = 1; i <= T->vertices; i  )
{
    if (T->parent[i] != -1)
    {
        printf("SSSP Distance from %d->%d is %d: {%d",
               T->visited[i], i, T->distance[i], i);

        j = i;
        while(T->parent[j] != -1)
        {   //the path is printed backwards, but still in order.
            j = T->parent[j];
            printf("<-%d", j);
        }
        printf("}\n");
    }   
}

Consider adding a function:

static void path_printer(SomeType *T, size_t i)
{
    size_t j = T->parent[i];
    if (j != -1)
    {
        path_printer(T, j);
        if (T->parent[j] != -1)
            printf("->");
        printf("%d", i);
     }
}

and revise your loop to:

for (i = 1; i <= T->vertices; i  )
{
    if (T->parent[i] != -1)
    {
        printf("SSSP Distance from %d->%d is %d: {",
               T->visited[i], i, T->distance[i]);
        path_printer(T, i);
        printf("}\n");
    }   
}

The recursive function prints the list items in reverse order; the rest is cosmetic.

^{Caution: untested code!}

^{Since the question does not provide an MCVE (Minimal, Complete, Verifiable Example — or MRE or whatever name SO now uses) or an SSCCE (Short, Self-Contained, Correct Example — the same idea by a different name), it is not possible to test this proposed solution. I had to guess the name of the type of the variable T — I think it is a SomeType *.}