Dijkstra算法求最短路径C#版

Dijkstra算法求最短路径（C#版）行如下图的路径，（vo是中心）：5VI.7252,V经过该算法后转化为下图26：2using System;using System.Collections;using System.Text;namespace Greedyclass Marxprivate int distance;private int row;private ArrayList ways = new ArrayList();public Marx(int n,params int d)this.row = n;distance = new introw * row;for (int i = 0; i row * row; i+)this.distancei =di;for (int i 二 0; i this.row; i+)/有 row个点，则从中心到各点的路有row-1条ArrayList w = new ArrayList();int j = 0; w.Add(j); ways.Add(w);/public void Find_way()ArrayList S = new ArrayList(1);ArrayList Sr = new ArrayList(1);int Indexof_distance=new intthis.row;for(int i=0; i row; i+)Indexof_distancei=i;S.Add( Indexof_distance0 );for (int i = 0; i 0)/假定中心点的编号是0的贪吃法求路径 for (int i = 0; i row; i+) Di = this.distancei;int min_num = (int)Sr0; /距中心点的最小距离点编号foreach (int s in Sr)s;if (Ds Dmin_num) min_num =/以上可以排序优化S.Add(min_num);Sr.Remove(min_num);/把最新包含进来的点也加到路径中);(ArrayList)waysmin_num).Add(min_num/foreach (int element in Sr)int position = element *bool exchange =(this.row) + min_num;false; /有交换标志if (Delement Dmin_num +this.distanceposition)Delement = Delement; elseDelement =this.distanceposition + Dmin_num;exchange = true; /修改距离矩this.distanceelementDelement;position = element * this.row;this.distanceposition = Delement;/修改路径if (exchange = true)(ArrayList)wayseleme nt).Clear();foreach (int point in (ArrayList)waysmin_num)(ArrayList)wa yselement).Add(point);-Count;/public void Display()/中心到各点的最短路径Console.Wri teLine(中心到各点的最短路径如下： nn);int sum_d_index = 0;foreach(ArrayList mother in ways)foreach (int child in mother)Console.Write(V0 - , child+1);Console.WriteLine(路径长0,distancesum_d_index+); class MainEnterPointstatic void Main(string args)int r; /列数Console.Write (请输入点个数(含配送中心点)：)； Int32.TryParse(Console.ReadLine(), out r); Console.Wri teLine(各点分别为：n);for (int i = 0； i r； i+) Console.Write(V0 , i);Console.Write( 假定第一个点是配送中心); Console.Wri teLine(nn输入各点之间的距离(无 通径的用个大整数表示八n)；int a = new intr * r; int da;for (int i = 0; i r; i+)for (int j = i + 1; j r; j+) Console.Wri te(V0到 V1的 距离是： ,i,j);Int32.TryParse(Console.ReadLin e(), out da);ai * r + j = da; Console.WriteLine();/完善距离矩阵(距离矩阵其实可以是个上三角矩阵，/但为了处理方便，还是将其完整成一个对称阵)for (int i = 0; i r; i+)for (int j = 0; j U ,leP）hhlll+1h过程2：模型生成过程基于过程1的数据驱动，将NP转化成为“剩余装载量”极小化为目标，以P 和FF为配载约束且仅以关于车辆选择变量t为决策变量的0-1规划模型（二 hhl（0-1） : min（hSt. 三 FF(15)ht e0,1,lEP (16)hln过程3：求解过程St epl：对(0-1)山求解，并基于“最优解”生成的“优选车辆集” p，计算 优先级最低车辆的“剩余装载量” FlhhStep2：基于需求矩阵CJ和满载要求，先按第三级优先准则，再按第四能优 先准则，以数据驱动方式对“优先车辆集” P中的车辆进行配载，生成x的hhlk(2)值得说明的n个问题： 关于0-1规划的求解比较成熟，后面讨论 对优先级最低车辆的剩余装载量的继续配载5基于对分搜索(0-1)的求解过程：(如图所示)h基于上述优化模型,NP问题已经转化为基于优先级循环调用折半查找（对分搜索） 的过程,各类的实现已经编译成 .dll, 该程序中包括一个通用排序类,寻找最优上界的 折半查找方法，和Dijkstra算法找配送中心到各配送点最短路径以形成配送路径网络的类.是测试代码: class MainEnterPointpublic void Default_Input()int r; /列数 r = 7;int a = new int0,2,3,5,99,99,5,9,7,99,5,99,99,5,99,0,2,7,2,0,1,7,1,0;2,0,99,2,93,99,0,99,5,2,99,0,399,99,5,3,99,7,99,5,5,99,99,99Marx m = new Marx(r, a); m.Find_way(); Console.WriteLine();Console.Wri teLine(生成路径图：n); /web w1 = new web();ArrayList webWay1 = new ArrayList(); m.Outway(out webWay1);w1.SetWays(webWay1);int b = new intr * r; m.Outdistance(out b); w1.SetDistance(b);w1.displayWeb();int s = new int 250, 350 ; Center c = new Center(s);Console.WriteLine(n 配送中心：n); c.displayS();/测试配送点 int index1 = 1;DateTime ts1 = new DateTime2; ts10 = new DateTime(2007, 1, 5); ts11 = new DateTime(2007, 2, 13); int rs1 = new int4 6, 3, 5, 7 ;int index2 = 2;DateTime ts2 = new DateTime2 new DateTime(2007,1,5), new DateTime(2007,3,8);int rs2 = new int4 8, 7, 1, 0 ;int index3 = 3;DateTime ts3 = new DateTime2 new DateTime(2007,1,5), new DateTime(2007,2,6);int rs3 = new int4 18, 7, 4, 3 ;int index4 = 4;DateTime ts4 = new DateTime2 new DateTime(2007,1,6), new DateTime(2007,2,16);int rs4 = new int4 7, 6, 14, 13 ;int index5 = 5;DateTime ts5 = new DateTime2 new DateTime(2007,1,15), new DateTime(2007,3,6);int rs5 = new int4 17, 2, 0, 1 ;int index6 = 6;DateTime ts6 = new DateTime2 new DateTime(2007,2,5), new DateTime(2007,4,6);int rs6 = new int4 0, 16, 2, 3 ;A_point points = new A_point6new A_point(m,index1,ts1,rs1),new A_point(m,index2,ts2,rs2),new A_point(m,index3,ts3,rs3),new A_point(m,index4,ts4,rs4), new A_point(m,index5,ts5,rs5), new A_point(m,index6,ts6,rs6);/测试车辆 car cars = new car10newcar(1,10),newcar(2,13),newcar(3,18),newcar(4,27),newcar(5,28),newcar(6,20),newcar(7,10),newcar(8,11),newcar(9,17),newcar(10,15)/NPdeal np = new NPdeal(w1, c, points, cars); np.run1(); public void Self_Input()int r; /列数Console.Write (请输入点个数(含配送中心点)：); Int32.TryParse(Console.ReadLine(), out r); Console.Wri teLine(各点分别为：n);for (int i = 1; i = r; i+) Console.Write(V0 , i);Console.Wri te(假定第一个点是配送中心)； Console.Wri teLine(nn输入各点之间的距离 (无通径的用相对大整数表示)n)；int a = new intr * r; /定义距离矩阵int da;for (int i = 0; i r; i+) /输入各点之 间的距离for (int j = i + 1; j r; j+)Console.Write(V0 到 V1的距离是: , i + 1, ine(), out da);角矩阵，阵)对象成路径j + 1);Int32.TryParse(Console.ReadLai * r + j = da;Console.WriteLine();/完善距离矩阵（距离矩阵其实可以是个上三/但为了处理方便，还是将其完整成一个对称for (int i = 0; i r; i+) for (int j = 0; j r; j+)if (i = j)ai * r + j = 0;aj * r + i = ai * r + j; Marx m = new Marx(r, a); /新建一个找路径m.Find_way(); /生Console.Wri teLine(生成路径图：n);web w1 = new web();ArrayList webWay1 = new ArrayList();m.Outway(out webWay1);w1.SetWays(webWay1);int b = new intr * r;m.Outdistance(out b);w1.SetDistance(b);w1.displayWeb();/路径网络创建完毕/Console.Wri teLine(n输入配送中心货物数目:); int types;Int32.TryParse(Console.ReadLine(), out types);int s = new inttypes;Console.WriteLine(输入各种货物库存量：)； for (int i = 0; i types; i+)si);Int32.TryParse(Console.ReadLine(), outCenter c = new Center(s)；Console.WriteLine(n 配送中心：n); c.displayS()；/配送中心数据输入完毕/int pNo = r - 1;A_point points = new A_pointpNo; Console.Wri teLine(n 录入配送点数据：n); for (int i = 0; i pNo; i+)Console.Wri te(V0点的交货期个数是：, i + 2);int times = 0; Int32.TryParse(Console.ReadLine(), out times);DateTime t = new DateTimetimes; string st;for (int j = 0; j times; j+) Console.Write(第0个交货日 期是(输入格式如： 2007/1/1)：, j + 1);st = Console.ReadLine();tj =DateTime.Parse(st); intrequires=newinttimes*types; int r_index = 0;for (int js = 0; js times; js+) Console.WriteLine(第0个交 货期对各货物的需求量为： ,js+1);for(intty=0;tytypes;ty+) Console.Wr it eLine(货物0: ,ty+1);Int32.TryParse(Console.ReadLine(), out requiresr_index+);pointsi = new A_point(m, i + 1, t, requires);/配送点录入完毕/Console.WriteLine();Console.Wri teLine(输入车辆数目：)； int carNum = 0;Int32.TryParse(Console.ReadLine(),outcarNum)； car cars = new carcarNum；Console.Wri teLine(输入各车载重量：)； for (int i = 0； i carNum； i+) int carWeight；Console.Wri te(车0 :, i + 1);Int32.TryParse(Console.ReadLine(), out carWeight)；carsi = new car(i + 1, carWeight)；/车辆录入完毕NPdeal np = new NPdeal(w1, c, points, cars)； np.run1()；static void Main(string args) Console.WriteLine(* 基于调运优先准则的物 流敏捷调运优化系统 *nn)；MainEnterPoint a = new MainEnterPoint()；Console.Wri teLine(按1、测试已有方案n按2、自 行录入方案n按3、退出)；int chose； while (true)Int32.TryParse(Console.ReadLine(), out chose)；if (chose = 1)a.Default_Input();else if (chose = 2) a.Self_Input();else break;程序流程补充说明1、本程序省去了一个步骤“对优先级最低车辆的剩余装载量的继续配载”，2、关于“当前可调用车辆集”的问题，车辆什么时候可用，什么时候不可用基 于以下原理:在当前配送地的路径上可能有多个点有相同的交货日期，若车X 被点P1用了，车的状态就设置为false,即该路径上与P1有相同交货日期的点 P2就不能调用车X，而当该路径上所有有相同交货日期的点都配送完成后，车X 的状态才会变成可用（true）例如在下图中，V2 V4 V5 是一条路径上的点，若这3个点有相同的交货日期，按照优先级2， 应该先给V5配送，所以，已经被V5所配载装满的车，就不能被V4或V2利用。3、关于空载率的说明，基于上述第一点，本程序求出的不是“修正后的空载率”， 而是每当一条路径上有相同交货日期的点配送完后，就根据车辆配载和剩余容量 统计出的空载率。如下图，V2 V4 V5若有相同交货日期，则对该日期的该路径上的点2，4，5配 送完成后，统计一下该路径的空载率。3、每次配载（即某一个点的一个交货期）完成后，程序会打印出剩余配送点的需求矩阵，（比较每次当前配送点的需求矩阵就可以看出差别），同时会打印出各车的各项参数，但程序有清屏功能，所以每次看屏幕要把滚动条拉到最上端再往下看。程序的默认方案如下所示：路径图：