topological sort + bellman

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int w;

int end;

struct node* next;

};

int visited[100];

struct node* adj;

int v,e;

int ordered[100];

int vertex;

int d[1000];

int p[1000];

void dfs(int i);

node* insert_adj(int a, int b, int w);

void topolo(int i);

void relax(int u,int v,int w);

int main(void)

{

int i,j;

int a,b,w;

FILE* fin = fopen("input.txt","r");

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+1));

for (i=0;i<=v;i++){

adj[i].end=-1;

adj[i].w=0;

adj[i].next=NULL;

d[i]=987654321;

p[i]=-1;

}

for (i=0;i<e;i++)

{

fscanf (fin,"%d %d %d",&a,&b,&w);

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

vertex=v-1;

topolo(0);

d[0]=0;

printf ("topological sort : ");

for (i=0;i<v;i++)

{

printf ("%d ",ordered[i]);

}

printf ("\n");

for (i=0;i<v;i++)

{

int cur = ordered[i];

node* temp = &adj[cur];

while( temp!=NULL && temp->end != -1){

relax(cur,temp->end,temp->w);

temp=temp->next;

}

}

printf ("dist : ");

for (i=0;i<v;i++)

{

printf ("%d ",d[i]);

}

printf ("\n");

return 0;

}

void relax(int u,int v,int w)

{

if (d[v]> d[u]+w)

{

d[v]=d[u]+w;

p[v]=u;

}

}

void topolo(int i)

{

node* temp=&adj[i];

visited[i]=1;

while(temp!=NULL)

{

if (visited[temp->end] == 0 && temp->end != -1)

{

topolo(temp->end);

}

temp=temp->next;

}

ordered[vertex--]=i;

}

node* insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == -1){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return &adj[a];

}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;

}

z = (node*)malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

return z;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != 0 )

{

if (visited[t->end] == -1){

dfs(t->end);

}

t=t->next;

}

}

}