注册 登录
编程论坛 C语言论坛

遍历了所有路径,如何加入路径和?

w的平方 发布于 2023-08-29 19:56, 495 次点击
程序代码:
#include<stdio.h>
#include<math.h>
int map[100][100]={0};
int stack[120],v[100]={0},top=0,m,n,start,end,L[100],Length=0;
void dfs(int pos)
{
    int i;
    if(pos==end){
        for(i=0;i<top;i++)
            printf("%d ",stack[i]);
        printf("%d\n",end);   
        for(i=0;i<top;i++)
        Length=L[stack[i]]+Length;
        printf("%d\n",Length);
        return;
    }
    v[pos]=1;
    stack[top++]=pos;
    for(i=1;i<=n;i++){
        if(!v[i]&&map[pos][i])
            dfs(i);
    }
    v[pos]=0;
    top--;
}

int main()
{
    int i,x,y,z;
    printf("分别输入顶点数n和路径数m:");
    scanf("%d %d",&n,&m);//n是顶点数,m是边数
   
    printf("输入m条路径及长度:");
    for(i=1; i<=m; i++) {
        scanf("%d %d %d", &x,&y,&z);
        L[i]=z;
        map[x][y] = 1;
        map[y][x] = 1;//无向图
    }
   
    printf("输入起始点和终点:");
    scanf("%d %d", &start,&end);
   
    printf("\n程序执行结果为:\n");
    dfs(start);
    return 0;}

不知道该怎么改求路径和?想得出每个路径的总长度,知道L[]的代码有问题,不知道怎么改?
2 回复
#2
w的平方2023-09-01 21:34
没人会嘛?
#3
forever742023-09-02 12:03
主要是书上有现成的,没必要。
程序代码:

#include <stdio.h>
#include <math.h>

int map[100][100] = { 0 };
int stack[120], v[100] = { 0 }, top = 0, m, n, start, end, L[100], Length = 0;
void dfs(int pos,int L1)
{
    int i;
    if (pos == end) {
        for (i = 0; i < top; i++)
            printf("%d ", stack[i]);
        printf("%d\n", end);

 //       for (i = 0; i < top; i++)

 
//           Length = L[stack[i]] + Length;
        printf("%d\n", L1);
        return;
    }
    v[pos] = 1;
    stack[top++] = pos;
    for (i = 1; i <= n; i++) {
        if (!v[i] && map[pos][i])
            dfs(i,L1+map[pos][i]);
    }
    v[pos] = 0;
    top--;
}

int main()
{
    int i, x, y, z;
    printf("分别输入顶点数n和路径数m:");
    scanf("%d %d", &n, &m);//n是顶点数,m是边数

    printf("输入m条路径及长度:");
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &z);

 //       L[i] = z;
        map[x][y] = z;
        map[y][x] = z;//无向图
    }

    printf("输入起始点和终点:");
    scanf("%d %d", &start, &end);

    printf("\n程序执行结果为:\n");
    dfs(start,0);
    return 0;
}
1