C语言及程序设计进阶例程-28 动态规划法问题求解

简介: 贺老师教学链接 C语言及程序设计进阶 本课讲解最短路径问题#include<stdio.h>#define n 7#define x 9999 /*用一个尽可能大的开销,代表结点之间没有通路*/int map[n][n]= /*对图7.33中交通网的描述,map[i][j]代表i结点到j结点的开销*/{ {x,4,5,8,x,x,x

贺老师教学链接 C语言及程序设计进阶 本课讲解

最短路径问题

#include<stdio.h>
#define n 7
#define x 9999  /*用一个尽可能大的开销,代表结点之间没有通路*/
int map[n][n]=   /*对图7.33中交通网的描述,map[i][j]代表i结点到j结点的开销*/
{
    {x,4,5,8,x,x,x},
    {x,x,x,6,6,x,x},
    {x,x,x,5,x,7,x},
    {x,x,x,x,8,9,9},
    {x,x,x,x,x,x,5},
    {x,x,x,x,x,x,4},
    {x,x,x,x,x,x,x}
};

int main()
{
    int cost[n]; /*记录出发点到每个结点的最短路径*/
    int path[n]= {0};  /*记录到达各个结点的最短路径中,上一个结点的编号*/
    int i,j;
    int minCost, minNode;
    cost[0]=0;     /*出发点到自己的开销为0*/
    for(i=1; i<n; i++)   /*循环过程中,求出到每个结点的最小开销,并且记录使开销最小的前一结点*/
    {
        minCost=x;
        for(j=0; j<i; j++)
        {
            if(map[j][i]!=x)
                if((cost[j]+map[j][i])<minCost)
                {
                    minCost=cost[j]+map[j][i];
                    minNode=j;
                }
        }
        cost[i]=minCost;
        path[i]=minNode;
    }
    printf("最短路径的开销为:  %d\n",cost[n-1]);  /*输出最短路径的开销*/

    printf("从终点向前推,最短路径经过了: ");
    i = n-1;   /*n-1就是终点的编号,本例中,n值为7*/
    while(i!=0) 
    {
        printf(" %d",path[i]);    /* 输出最短路径上前一个结点的编号*/ 
        i = path[i];    /*从刚输出的结点,再循环向前倒推*/
    }
    printf("\n");
    return 0;
}
目录
相关文章
|
16小时前
|
算法 C语言 C++
C语言进阶:冒泡排序函数初步实现
C语言进阶:冒泡排序函数初步实现
|
16小时前
|
C语言
C语言进阶:进阶指针(下)
C语言进阶:进阶指针(下)
|
16小时前
|
C语言
C语言进阶:指针的进阶(上)
C语言进阶:指针的进阶(上)
|
16小时前
|
存储 C语言
C语言进阶 数据的存储(上)
C语言进阶 数据的存储(上)
|
6天前
|
存储 开发框架 编译器
C语言进阶—自定义类型:结构体,枚举,联合
C语言进阶—自定义类型:结构体,枚举,联合
|
6天前
|
存储 C语言 C++
C语言进阶——指针
C语言进阶——指针
|
6天前
|
存储 小程序 编译器
C语言进阶—深度剖析数据在内存中的存储
C语言进阶—深度剖析数据在内存中的存储
|
7天前
|
存储 编译器 C语言
C语言程序设计——字符输入函数getchar()
C语言程序设计——字符输入函数getchar()
|
7天前
|
存储 编译器 C语言
C语言程序设计——字符输出函数putchar()
C语言程序设计——字符输出函数putchar()
|
7天前
|
程序员 C语言
C语言程序设计——循环语句
C语言程序设计——循环语句