Question

Usually, Djikstra’s shortest-path algorithm is not used on graphs with negative-weight edges because it may fail and give us an incorrect answer. However, sometimes Djikstra’s will give us the correct answer even if the graph has negative edges.
You are given graph G with at least one negative edge, and a source s. Write an algorithm that tests whether Djikstra’s algorithm will give the correct shortest paths from s. If it does, return the shortest paths. If not, return ‘no.’ The time complexity should not be longer than that of Djiksta’s algorithm itself, which is Θ(|E| + |V | log |V |).
(Hint: First, use Djikstra’s algorithm to come up with candidate paths. Then, write an algorithm to verify whether they are in fact the shortest paths from s.)

Answer 1

#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10
 
void dk(int L[MAX][MAX],int n,int sn);
 
int main()
{
        int L[MAX][MAX],i,j,n,u;
        printf("Enter the number of vertices:");
        scanf("%d",&n);
        printf("\nEnter the adjacency matrix:\n");
        
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        scanf("%d",&L[i][j]);
        
        printf("\nEnter your starting node:");
        scanf("%d",&u);
        dk(L,n,u);
        
        return 0;
}
 
void dk(int L[MAX][MAX],int n,int sn)
{
 
        int cost[MAX][MAX],distance[MAX],pred[MAX];
        int visited[MAX],count,mindistance,nextnode,i,j;
        
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        if(L[i][j]==0)
                                cost[i][j]=INFINITY;
                        else
                                cost[i][j]=L[i][j];
        
        //initialize pred[],distance[] and visited[]
        for(i=0;i<n;i++)
        {
                distance[i]=cost[sn][i];
                pred[i]=sn;
                visited[i]=0;
        }
        
        distance[sn]=0;
        visited[sn]=1;
        count=1;
        
        while(count<n-1)
        {
                mindistance=INFINITY;
                
                
                for(i=0;i<n;i++)
                        if(distance[i]<mindistance&&!visited[i])
                        {
                                mindistance=distance[i];
                                nextnode=i;
                        }
                        
                        visited[nextnode]=1;
                        for(i=0;i<n;i++)
                                if(!visited[i])
                                        if(mindistance+cost[nextnode][i]<distance[i])
                                        {
                                                distance[i]=mindistance+cost[nextnode][i];
                                                pred[i]=nextnode;
                                        }
                count++;
        }
 
        for(i=0;i<n;i++)
                if(i!=sn)
                {
                        printf("\nDistance of node%d=%d",i,distance[i]);
                        printf("\nPath=%d",i);
                        
                        j=i;
                        do
                        {
                                j=pred[j];
                                printf("<-%d",j);
                        }while(j!=sn);
        }
}

Hope I answered the question.

If you have any doubts, or queries, feel free to ask

I'll respond to you as soon as I can.

Have a nice day