shortestpathsedge

来自「In some graphs, the shortest path is giv」· 代码 · 共 295 行

Shortest Paths with Edge Metrics. In some graphs, the shortest path is given by optimizing two different metrics: the sum of weights of the edges and the number of edges. For example: if two paths with equal cost exist then, the path with the least number of edges is chosen as the shortest path. Given this metric, you have find out the shortest path between a given pair of vertices in the input graph. The output should be the number of edges on the path, the cost of the shortest path, and the path itself. Input is the adjacency matrix and the two vertices.
Input:
5
0 1 0 1 0
1 0 2 0 0
0 2 0 0 3
1 0 0 0 2
0 0 3 2 0
1 5
Output:
2
3
1->4->5

solution

#include<stdio.h>
#include<stdlib.h>

struct Stk
{
int* q;
int top;
};

struct Node
{
int cost;
struct Stk *st;
struct Node *next;
};

struct Stk *st=NULL;
struct Node *nd = NULL;
struct Node *head = NULL;

void push(int i, int n)
{
/*printf("inside push %d \n",i);*/
if(isempty()==-1)
{
st->q= (int*)malloc(sizeof(int)*n);

}
st->top++;
st->q[st->top]=i;
}

int pop()
{

int res;
/*printf("inside pop ");;*/
if(isempty()==-1)
{
return -1;
}
res = st->q[st->top];
/*printf("%d\n",res);*/
st->top--;
return res;

}

int isempty()
{
if(st->top==-1)
return -1;
else
return 0;
}

void copyStk(struct Stk* t, struct Stk* st, int n)
{
int i;
/*printf("inside copystk\n");*/


t->q = (int*)malloc(sizeof(int)*n);
for(i=0;i<=st->top;i++)
{
t->q[i]=st->q[i];
}
t->top= st->top;
/*printf("t->top is %d\n",t->top);*/
}
void printq(int n, int cost)
{
int i,setval,cnt;
struct Node* nd1;
struct Node* prev;

prev= NULL;
nd1=NULL;

setval=0;
if (nd==NULL)
{
/*printf("inside if printq\n");*/
nd=(struct Node*)malloc(sizeof(struct Node));
head = nd;
/*printf("st->top is %d\n",st->top);*/
nd->cost = cost;
/*nd->st = st;*/
nd->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd->st,st,n);
/*printf("nd->st->top is %d\n",nd->st->top);*/
}
else
{
/*printf("inside else printq\n");*/
nd = head;
cnt = st->top;
/*printf("cnt is %d\n",cnt);*/
prev = head;
while(nd != NULL)
{
if(cost < nd->cost)
{
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->cost = cost;
/*printf("st->top is %d\n",st->top);*/
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
nd1->next = nd;

if(head==nd)
head = nd1;
else
prev->next=nd1;

setval=1;
break;
}
if(cost>=nd->cost)
{
prev=nd;
nd = nd->next;
}
}

if(setval==0)
{
/*printf("inside setval printq\n");*/
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->cost = cost;
printf("st->top is %d\n",st->top);
/*nd1->st = st;*/
nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
prev->next=nd1;
}


}


}

/*void reset(int arr[][3],int n)*/
void reset(int** arr,int n)
{
int i,j;
i=j=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]==-1)
arr[i][j]=1;
}

}
free(st->q);
st->top=-1;
head=NULL;
nd = NULL;
}

/*int dfs(int src,int dest, int arr[][3], int n, int cnt)*/
int dfs(int src,int dest, int** arr, int n, int cnt, int cost)
{
int i,val;


for(i=0;i<n;i++)
{
val = arr[src][i];
if(arr[src][i]>0)
{
push(i,n);
cost = cost + val;
arr[src][i]=-arr[src][i];
arr[i][src] = -arr[i][src];
if(i==dest)
{
cnt++;
/*printf("%d\n",cnt); */
printq(n,cost);
}
else
cnt = dfs(i,dest,arr,n,cnt,cost);
cost = cost-val;
pop();
}
}
return cnt;


}

int main()
{
int notestcases;
int src,dest, i,j,n,cnt;
int** arr;
int* srcArr;
int* destArr;
/*int arr[][3] = {{0,1,1},{0,0,1},{0,0,0}};*/
i=0;j=0;

st= (struct Stk *)malloc(sizeof(struct Stk));
st->top=-1;

scanf("%d",&n);

if(n > 0)
{
arr = (int**) malloc(sizeof(int*)*(n));


for(i=0;i<n+1;i++)
arr[i]=(int*)malloc(sizeof(int)*(n));


for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{

scanf("%d",&arr[i][j]);

}

}





i=0;


scanf("%d %d",&src, &dest);
cnt = 0 ;


src--;dest--;
if (src == dest)
{
printf("%d\n",src);
return 0;
}
push(src,n);
cnt  = dfs(src,dest,arr,n,0,0);


nd = head;
if(nd != NULL)
{
printf("%d\n",nd->st->top );
printf("%d\n",nd->cost);
for(i=0;i<=nd->st->top;i++)
{
printf("%d",(nd->st->q[i])+1);
if(i < nd->st->top)
printf("->");
}
printf("\n");


}


/*reset(arr,n);*/




}/*if n>0*/

return 0;
}