Matlab实现分支定界法 过路费约束 最短路径

题目描述和数据都打包了。作业题，matlab实现。 某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城 市。甲城市与乙城市之间共有 n 座城市，互相以公路连通。甲城市、乙 城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵 M1 给出。 每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩 阵M2 给出。 请给出在需付养路费总额不超过 1500 的情况下，该公司货车运送其 产品从甲城市到乙城市的最短运送路线。

%%Assignment 2 张天宇 BY1706135

global path; %DFS函数中使用变量，记录当前路径
global dest; %目的地点，本题中为50
global mark; %标记是否访问过，DFS函数中使用
global A; %原始数据，m1.txt 邻接矩阵，9999改为inf
global B; %原始数据，m2.txt cost矩阵，9999改为inf
global shortestpath; %长度为50的数组，记录各个城市到目标城市的最短路径长度
global minimumcost; %长度为50的数组，记录各个城市到目标城市的最小代价
global dis_low;%路径长度下界
global max_cost;%cost最大为1500
global path_best;%记录最短路径
global cost_best;%记录最短路径的Cost
max_cost=1500;
dis_low=inf;
load m1.txt;
load m2.txt;
m1（m1==9999）=inf;

m2（m1==inf）=inf;


shortestpath=zeros（（[150]））;
minimumcost=zeros（（[150]））;

for i=1:50
    shortestpath（i）=dijkstra（m1i50）;
    minimumcost（i）=dijkstra（m2i50）;
end

mark=zeros（[150]）;
dest=50;
path=zeros（[150]）;
A=m1;
B=m2;

dfs（100）; %深度优先遍历所有路径

disp（[‘最短路径长度：‘num2str（dis

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-01-09 11:40  Assignment_2\
     文件        3329  2018-01-09 11:38  Assignment_2\Assignment_2.m
     文件        7942  2005-12-06 01:13  Assignment_2\Assignment_2.pdf
     文件       12010  2005-04-10 12:07  Assignment_2\m1.txt
     文件        8861  2005-04-10 12:08  Assignment_2\m2.txt