精华内容
下载资源
问答
  • [算法]多段图最短路径 多段图最短路径问题是应用动态规划的经典问题之一,许多优化问题都能转化为多段图最短路径问题进而求解。多段图最短...

    [图算法]多段图最短路径

    多段图最短路径问题是应用动态规划的经典问题之一,许多优化问题都能转化为多段图最短路径问题进而求解。多段图最短路径的问题描述如下:

    问题描述

    设G=(V,E)是一个赋权有向图,其顶点集V被划分为k个不相交的子集Vi(1<=i<=k),其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中, 且边(u,v)有一个正权重,记为w(u,v).请设计一个算法,求解从源s到汇t的权重之和最小的路径。

    多段图最短路径示意图

    问题分析

    此问题具有最优子结构性质:假如1–2–7–10–12为上图中源节点1到汇节点12的一条最短路径,那么1–2–7–10一定为节点1到节点10的最短路径(反证法可以证明)。所以此问题适用于动态规划算法。
    这里写图片描述

    设w(i,p)为源节点s到节点v(i,p)的最短路径代价(i指阶段序号,p指第i阶段中的节点序号),而节点v(i+1,q)为节点v(i,p)的一个后继节点(所谓后继节点,即v(i+1,q)为v(i,p)下一阶段的一个节点,且v(i,p)到v(i+1,q)之间有一条路径。因为v(i,p)的后继节点可能有多个,所以设v(i+1,q)为“其中一个”后继节点。同理,称节点v(i,p)为节点v(i+1,q)的一个前驱结点)。则从源节点经由节点v(i,p)到节点v(i+1,q)的路径代价为w(i,p)+w(p,q)。当遍历v(i+1,q)的所有前驱节点后,会计算出一个最小的代价值,把它作为w(i+1,q)的值。把上述逻辑用数学递推式来表示为:
    这里写图片描述

    问题求解

    采用自底向上的动态规划算法进行求解,先求解源s到第2阶段所有节点的最短路径,然后求第3阶段所有节点的最短路径,以此类推,直到求到汇节点t,即为我们所要求的值。程序中,我们采用一张表格(二维数组)来存储各个节点到源节点s的最短路径值。这样,我们能求出最短路径的值,如果还需要求具体的路径,则还需要维护一张表格,记录路径中的节点号。

    以下程序摘自互联网资源 http://blog.csdn.net/u012432778/article/details/41623961 ,我没有亲自验证,不保证完全正确。

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MaxState 100
    
    int minRoad[MaxState][MaxState];
    void multiStageGraph(int stageNum, int *numPerStage);
    
    int main()
    {
        int i, k, ni[MaxState];
        while(scanf("%d", &k),k != -1)
        {
            for(i = 0; i < k; ++i)
            {
                scanf("%d", &ni[i]);
            }
            multiStageGraph(k, ni);
        }
        return 0;
    }
    
    void multiStageGraph(int stageNum, int *numPerStage)
    {
        int i, q, p, weight, temp;
        memset(minRoad, 0x3f, sizeof(minRoad));           //初始化为一个充分大的数0x3f
    
        for (p = 0; p < numPerStage[0]; ++p)              //初始化源顶点层
        {
            minRoad[0][p] = 0;
        }
    
        for (i = 0; i < stageNum - 1; ++i)                //按段计算,终止与汇顶点的前一段
        {
            for (q = 0; q < numPerStage[i]; ++q)          //遍历第i段顶点
            {
                for (p = 0; p < numPerStage[i + 1]; ++p)  //遍历第i+1段顶点
                {
                    scanf("%d", &weight);                 //读取边(q,p)的权重w(q,p)
                    if (weight != -1)                     //存在边(q,p)
                    {
                        temp = minRoad[i][q] + weight;
                        if (temp < minRoad[i+1][p])       //发现s到o的更短路径
                        {
                            minRoad[i+1][p] = temp;
                        }
                    }
                }
            }
        }
        printf("%d\n", minRoad[stageNum-1][0]);
    }
    
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    参考资料:
    [1] http://blog.csdn.net/u012432778/article/details/41623961
    [2] 算法导论第六部分:图算法

    展开全文
  • 多段图最短路径,算法课的一个小实验 先利用最优性原理找出所有节点最短路径长度 再利用所有节点的最短路径长度通过回溯的方法找到所有最短的路径
  • 多段图最短路径问题

    千次阅读 2015-06-05 12:41:28
    多段图最短路径java语言实现

    A multistage graph is a graph (1) G=(V,E)with V partitioned into K >= 2 disjoint subsets such that if (a,b) is in E,then a is in Vi , and b is in Vi+1 for some subsets in the partition; and (2) | V1 | = | VK | = 1.

    多段图java解法:

    package com.secondwork;
    /**
     * 多段图解法
     * @author YR
     *
     */
    public class Test5 {
        private static int  n = 16;
        private static int[][] arr= {
                {0,5,3,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {5,0,0,1,3,6,0,0,0,0,0,0,0,0,0,0},
                {3,0,0,0,8,7,6,0,0,0,0,0,0,0,0,0},
                {0,1,0,0,0,0,0,6,8,0,0,0,0,0,0,0},
                {0,3,8,0,0,0,0,3,5,0,0,0,0,0,0,0},
                {0,6,7,0,0,0,0,0,3,3,0,0,0,0,0,0},
                {0,0,6,0,0,0,0,0,8,4,0,0,0,0,0,0},
                {0,0,0,6,3,0,0,0,0,0,2,2,0,0,0,0},
                {0,0,0,8,5,3,8,0,0,0,0,1,2,0,0,0},
                {0,0,0,0,0,3,4,0,0,0,0,3,3,0,0,0},
                {0,0,0,0,0,0,0,2,0,0,0,0,0,3,5,0},
                {0,0,0,0,0,0,0,2,1,3,0,0,0,5,2,0},
                {0,0,0,0,0,0,0,0,2,3,0,0,0,6,6,0},
                {0,0,0,0,0,0,0,0,0,0,3,5,6,0,0,4},
                {0,0,0,0,0,0,0,0,0,0,5,2,6,0,0,3},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,4,3,0},
        };
        
        //使用向后递推算法求多段图的最短路径
        public static void shortPath(int arr[][]){
    int i = 1;
    int sum = 0;
    int temp = 0;
    int p [] = new int[n];
    int len[] = new int[n];
    while(i<n){
       int total = Integer.MAX_VALUE;
       for(int j =0;j<i;j++){
    if(arr[j][i]!=0){
    //判断是否存在到该节点的路径,如果有则根据路径长度更新
       if(total>(arr[j][i]+len[j])){
    total = arr[j][i]+len[j];
    temp = j;
       }
       len[i] = total;
       sum = total;
       p[i] = temp;
    }
       }
       i++;
    }
    int path[] = new int[7];//此图段数为7段
    path[0] = 0;
    path[6] = 15;
    for(int k = 5;k>=1;k--){
       path[k] = p[path[k+1]];
    }
    System.out.println("最短路径为:");
    for(int m = 0;m<6;m++){
       System.out.print(path[m]+"->");
    }
    System.out.println(path[6]);
    System.out.println("最小代价为:"+sum);
        }
        public static void main(String[] args) {

    shortPath(arr);

        }
    }

    结果:

    最短路径为:
    0->1->4->7->11->14->15
    最小代价为:18

    展开全文
  • 多段图最短路径

    千次阅读 2014-11-30 16:42:46
    问题描述:设是一个赋权有向,其顶点集V被划分为个不相交的子集,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中:, 且边(u,v)有一个正...

    问题描述:设是一个赋权有向图,其顶点集V被划分为个不相交的子集,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中:, 且边(u,v)有一个正权重,记为.请设计一个算法,求解从源s到汇t的权重之和最小的路径。


    状态表示

    包含源s的子图都可以认为是一个子问题,子图的源是固定的,汇是可以变化的。因此,确定了汇的位置,则能确定一个子图。汇的位置包括两个参数:段的序号和该段顶点集合中汇顶点的序号。

    W(i,p)表示从源s 到v(i,p) 的最短路径长度

    ui(1≤i≤k)表示段的序号
    up(1≤p≤n_i)表示第 i 段顶点集中的顶点序号

    状态递推方程


    最优值求解

    u子问题的数目等于图G中 顶点的个数
    u采用 自底向上的方法求最优值,最开始求解源s到第2段顶点集中每一个顶点的最短路径。这是最简单的子问题,最优值就等于边长。
    然后求解s到第3段顶点集中的每一个顶点的最优值,依此循环,直至求解s到t的最短路径值


    输入:包含多组测试数据。每组测试数据第一行输入正整数k(k<100), 表示不相交子集的数目。第二行包含k个正整数ni(1<=i<=k),分别表示每一个顶点集Vi(1<=i<=k)中顶点的数目(不超过100)。紧接着k-1行记录相邻顶点集合间边的权重。其第i(1<=i<k)行包含niXni+1个数,表示顶点集Vi和Vi+1之间的边的权重(-1表示没有边相连),权重矩阵按行排列,也就是Vi中第p(1<=p<ni)个顶点和Vj中第q(1<=q<ni)个顶点之间的权重对应行第(p-1)Xnj+q和位置的值。最后一行输入-1,表示输入结束。


    输出:每组测试数据的结果输出占一行,输出其最小的权重值。


    样例输入:

    5

    1 4 3 3 1

    9 7 3 2

    4 2 1 2 7 -1 -1 -1 11 -1 11 8

    6 5 -1 4 3 -1 -1 5 6

    4 2 5 

    -1

    程序如下:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MaxState 100
    
    int minRoad[MaxState][MaxState];
    void multiStageGraph(int stageNum, int *numPerStage);
    
    int main()
    {
        int i, k, ni[MaxState];
        while(scanf("%d", &k),k != -1)
        {
            for(i = 0; i < k; ++i)
            {
                scanf("%d", &ni[i]);
            }
            multiStageGraph(k, ni);
        }
        return 0;
    }
    
    void multiStageGraph(int stageNum, int *numPerStage)
    {
        int i, q, p, weight, temp;
        memset(minRoad, 0x3f, sizeof(minRoad));           //初始化为一个充分大的数0x3f
    
        for (p = 0; p < numPerStage[0]; ++p)              //初始化源顶点层
        {
            minRoad[0][p] = 0;
        }
    
        for (i = 0; i < stageNum - 1; ++i)                //按段计算,终止与汇顶点的前一段
        {
            for (q = 0; q < numPerStage[i]; ++q)          //遍历第i段顶点
            {
                for (p = 0; p < numPerStage[i + 1]; ++p)  //遍历第i+1段顶点
                {
                    scanf("%d", &weight);                 //读取边(q,p)的权重w(q,p)
                    if (weight != -1)                     //存在边(q,p)
                    {
                        temp = minRoad[i][q] + weight;
                        if (temp < minRoad[i+1][p])       //发现s到o的更短路径
                        {
                            minRoad[i+1][p] = temp;
                        }
                    }
                }
            }
        }
        printf("%d\n", minRoad[stageNum-1][0]);
    }
    




    展开全文
  • 动态规划求解多段图最短路径 题目: 分析见源代码注释 源代码: #include<stdio.h> #define N 10//定义定点数,编号从1开始 #define M 5//定义层数 #define INF 0x3f3f3f int graph[100][100];//的链接矩阵 ...

    动态规划求解多段图最短路径

    题目:
    在这里插入图片描述
    分析见源代码注释
    源代码:

    #include<stdio.h>
    #define N 10//定义定点数,编号从1开始
    #define M 5//定义层数
    #define INF 0x3f3f3f
    int graph[100][100];//图的链接矩阵
    int num[5] = { 1,4,7,9,10 };//每一层对应的节点最大编号,用于区分每一层
    int cost[N+1];//每一个节点从起点到该节点的最短距离
    int pos[N + 1];//每一个节点对应最短距离的上一节点,用于后续输出最短路径
    void map()
    {
    	int i,x;
    	for (i = 0; i < M-1; i++)//对应每一层,从第二层开始
    	{
    		x = num[i] + 1;
    		while (x <= num[i + 1])//每一层的每个节点
    		{
    			for (int j = 1; j <= 10; j++)//遍历与该节点有链接关系的上一层节点
    			{
    				if (graph[j][x] != 0)
    				{
    					int y = graph[j][x] + cost[j];//该层节点与上一层节点间距离+起点到上一层的最短距离
    					if (y < cost[x])//比较大小,求出起点到该节点的最短距离
    					{
    						cost[x] = y;
    						pos[x] = j;
    					}
    				}
    			}
    			//printf("%d ", cost[x]);//输出每一个节点对应的最短路径代价
    			x++;
    		}
    	}
    }
    void showpath()//输出最短路径
    {
    	int i = N,j=0;
    	int a[M-1];
    	while (i > 1)
    	{
    		a[j++] = pos[i];
    		i = pos[i];
    	}
    	printf("最短路径为:");
    	for (i = M - 2; i >= 0; i--)
    		printf("%d->", a[i]);
    	printf("%d\n",N);
    }
    int main()
    {
    	for (int i = 1; i <= N; i++)
    	{
    		cost[i] = INF;
    		pos[i] = 1;
    	}
    	cost[1] = 0;
    	pos[1] = 0;
    	for (int i = 1; i <= N; i++)
    		for (int j = 0; j <= N; j++)
    			graph[i][j] = 0;
    	graph[1][2] = 4; graph[1][3] = 2; graph[1][4] = 3;//初始化
    	graph[2][5] = 10; graph[2][6] = 9;
    	graph[3][5] = 6; graph[3][6] =7; graph[3][7] =10;
    	graph[4][6] = 3; graph[4][7] =8;
    	graph[5][8] = 4; graph[5][9] = 8;
    	graph[6][8] = 9; graph[6][9] =6;
    	graph[7][8] = 5; graph[7][9] = 4;
    	graph[8][10] = 8; 
    	graph[9][10] = 4;
    	map();
    	showpath();
    	printf("代价为:%d", cost[N]);
    	return 0;
    }
    
    展开全文
  • #include //#define LEN sizeof(struct NODE) #define N 10 #define MAX_TYPE 10000 #define ZERO_TYPE 0 /*定义的邻接链表*/ struct NODE /*邻接表.../*在阶段决策中,各个顶点到收点的最短路径上的前方顶点编号*/
  • 动态规划--多段图最短路径

    万次阅读 2017-10-29 12:50:17
    问题描述:设是一个赋权有向,其顶点集V被划分为个不相交的子集,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi+1中:, 且边(u,v)有一个正...
  • 多段图的最小成本问题 实验要求 设G=(V,E)是一个赋权有向,其顶点集V被划分成k>2个不相交的子集Vi: 1ik,其中,V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇),中所有的边(u,v)的始点和终点都在相邻的两...
  • 多段图最短路径问题 多段图最短路径问题
  • 最短路径啊呼呼湖花海爱看哦家具i及oak卡机骄傲交接才奇偶经常哦撒娇哦i就死哦
  • 最短路径问题---Dijkstra算法详解

    万次阅读 多人点赞 2017-03-08 16:42:46
    前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ...从中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法:...
  • 动态规划多段图最短路径问题,希望大家下载给我加点分啦。希望大家下载给我加点分啦。希望大家下载给我加点分啦。 (C语言源程序),
  • 多段图最短路径

    2018-04-04 14:18:23
    多段图是一个有向的无环。求解从起始点v0到终止点的最短路径的长度,首先看一下这个问题是否具有最优子结构的性质。对于每一点来说,从v0到它的最短路径有两种可能,分别是从v0直接到该点或者是从最短的前驱节点...
  • C++多段图最短路径

    2010-05-09 11:46:48
    C++多段图最短路径程序实现 #include #define INFINITY 32767 #define MAX 20 typedef struct { char vexs[MAX]; //顶点信息 int vexnum,arcnum; int arcs[MAX][MAX]; }Graph;//的结构体
  • 最短路径问题 大一数据结构最短路径问题
  • 在一个带权中,顶点V0到中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。 DiskStra算法: 求单源最短路径,即求一个顶点到任意顶点的...
  • 最短路径算法最短路径算法最短路径算法最短路径算法
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 1. 我们在使用Dijkstra算法求解源点到其余顶点的最短路径的时候,在大多数情况下最短路径是只有一条的,但是也有可能存在着最短路径的情况,所以之前使用整型的pre[]数组来记录当前节点的前驱节点的方法就不再...
  • 地图最短路径代码

    2019-03-09 18:45:49
    有一张地图,找出任意两点之间的最短路径
  • 最短路径最短路径树和最小生成树

    万次阅读 多人点赞 2018-06-07 09:38:18
    首先介绍这三个概念,很多人都听过最短路径了,但是最短路径树却很少听过,关于最短路径树的介绍也不太。而最短路径树和最小生成树更是完全不同的两个概念。 最短路径就是从一个指定的顶点出发,计算从该顶点出发...
  • 无权最短路径 按照路径长度递增的顺序找出源点到各个顶点的最短路径 类似于BFS-宽度优先遍历,可以通过队列来实现, 先让顶点入队,循环执行下列步骤 出队首元素,访问其所有邻接点 标明源点到这些邻接点...
  • 迷宫图最短路径

    2012-03-31 21:04:44
    迷宫图最短路径
  • 多段图最短路径问题 问题:设G=(V,E)是一个带权有向,如果把顶点集合V划分成k个互不相交的子集Vi(2<=k<=n,1<=i<=k), 使得E中的任何一条边<u,v>,必有u∈Vi,v∈Vi+m(1<=i<k,1&...
  • 7.1 最短路径问题7.1.1 概述图论里最少的步骤就是最短路径问题。最短路径问题的抽象在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。... - (有向)有权多源最短路径问题:求任
  • 地图最短路径算法

    2019-03-24 23:28:35
    最短路径算法,做了堆优化有测试用例,可以随机生成地图,地图中的数字代表的是该点的高度,高度差为两点的距离
  • 要求:求带权有向中某一结点到其他结点的最短路径。 用迪杰斯特拉算法求解,迪杰斯特拉算法书上的描述如下: 对于G=(V,{E}),将中的顶点归为两组: 第一组S:已求出的最短路径的终点集合(开始为{v0}) 第...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 189,439
精华内容 75,775
关键字:

多段图最短路径