dijkstra

#include <stdio.h>

#include <stdlib.h>

struct node

{

int w;

int end;

struct node* next;

};

typedef struct node node;

struct heapnode

{

int end;

int val;

};

typedef struct heapnode heapnode;

node* adj;

int v,e;

int nearest[1000]; //-1

int dist[1000]; //infinite

int flag[1000];

struct heapnode heap[10000];

int heapsize;

void insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == 0){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return;}

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;

}

void siftdown(int i)

{

struct heapnode siftkey = heap[i];

int parent = i;

int found=0;

int largerchild;

while((2* parent < heapsize) && !found)

{

if ( (2*parent < heapsize) && (heap[2*parent].val > heap[2*parent+1].val ) )

largerchild = 2*parent+1;

else

largerchild = 2* parent;

if (siftkey.val > heap[largerchild].val )

{

heap[parent] = heap[largerchild];

parent = largerchild;

}

else

found = 1;

}

heap[parent] = siftkey;

}

heapnode root()

{

heapnode out = heap[1];

heap[1] = heap[heapsize];

heapsize--;

siftdown(1);

return out;

}

void insert_heap(heapnode t)

{

int parent;

int found=0;

int in;

heapsize++;

parent = heapsize/2;

in=heapsize;

while(parent > 0 && !found)

{

if (heap[parent].val > t.val)

{

heap[in]= heap[parent];

parent/=2;

in/=2;

}

else

found=1;

}

heap[in]= t;

//siftdown(heapsize);

}

void dij()

{

int i,near,min,e;

node* t;

heapnode ht;

for (int i=1;i<=v;i++){

nearest[i] = -1;

dist[i] = 987654321;

flag[i]=0;

}

dist[0]=0;

dist[1]=0;

ht.end=1;

ht.val=0;

insert_heap(ht);

for (int i=0 ; i < v-1 ; i++)

{

min=987654321;

do

{

ht=root();

t= &adj[ht.end];

}while (flag[ht.end]);

while(t != NULL)

{

if (!flag[t->end] && t->end !=1 && (dist[t->end] > t->w + dist[ ht.end ]))

{

heapnode tt;

nearest[t->end] = ht.end;

dist[t->end] = t->w + dist[ ht.end ];

tt.end=t->end;

tt.val=t->w;

insert_heap(tt);

}

t=t->next;

}

flag[ht.end]=1;

}

}

int main(void)

{

int i,sum=0;

int a,b,w;

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

node* t;

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

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

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

adj[i].end=0;

adj[i].w=0;

adj[i].next=NULL;

}

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

{

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

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

/*

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

{

t=&adj[i];

while(t!=NULL)

{

heapnode ht;

ht.end = t->end;

ht.val = t->w;

insert_heap(ht);

printf ("%d %d, ",t->end,t->w);

t=t->next;

}

printf ("\n");

}

printf ("\n");

for (i=0;i<=heapsize;)

{

heapnode t = root();

printf ("%d %d\n",t.end, t.val);

}

*/

dij();

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

{

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

sum+=dist[i];

}

printf ("\n");

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

{

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

}

return 0;

}