题目 破局共享汽车

自 2015 年以来，共享汽车行业曾经“百花齐放”，多个项目获得巨额融资。但因为模式过重、运营成本过高、无法盈利等问题，陆续有共享汽车公司因为资金链断裂而倒闭。据易观发布的《2019 中国共享汽车平台创新白皮书》显示，2019 年的共享汽车行业，是中小参与者不断出局，头部平台拉动行业重启增长的一年。而共享汽车增速在 2019 年 5–10 月达到 2.21%，超过网约车和线上租车。
据悉，共享汽车在市面上的停车位合作模式，主要是与停车场、小区进行合作。记者从共享汽车APP平台上了解到，联动云、gofun、摩范出行等共享汽车品牌都在优品汇停车场内设定停车位。从停车场的安保部门处获悉，该处网点有二十来个共享汽车车位，采用租赁方式出租给共享汽车公司。但是由于商场位于市中心繁华地段，看似二十多个车位颇多，往往一会就停满了。如果租赁车位已满，共享汽车便只能再行找其他停车场了。
共享汽车在租赁停车位时，不同平台会根据其公司战略规划和协商情况，在不同的网点租取不同个数的车位，一旦租的车位停满后，用户就无法进行还车。对于还车问题，记者通过各共享汽车品牌APP了解到，摩范出行采用“预约还车”的策略，gofun出行则采用“先到先得”的还车方式。

摩范出行的客服人员表示，“还车时需要提前预约，车位停满后不可再停，只能去其他网点还车。”但在调查中，有用户反映，开车到达一网点后，现场明明有还车位置，APP上却显示车位已满。对此，摩范出行的客服人员做出了解释，“因为这个车位已经被其他车主预约，即使车未到，仍然会为其保留车位。”不少用户表示不能理解，如果预约车主最后并未选择此处停车，就等于资源浪费，并且给其他车主带来了不便。

gofun出行针对此情况进行了另外一种尝试，“可以手动提前预约还车网点，但是还车网点的车位无法为用户保留，哪位用户先到达网点，就可先进行还车。”记者注意到，gofunAPP上除了显示免费停车位外，也有超停还车费用的标识。对此，客服人员解释，“即使免费停车位为0，也可以进行还车，但需要支付超停费用，价格为3-20元不等，是根据还车网点来决定的。”对于记者提出的还车难问题，客服人员表示，“确实存在这样的情况，非常抱歉对用户出行带来不便。”

相较于摩范、gofun在下单前即可查看剩余车位的模式，联动云租车APP上并未有此功能。“车位有限，只有在用户还车时才会显示剩余车位，用车前未下单是看不了的。”在APP上，一个停车网点上附有“部分免收取还车服务费（超停收费）”的字样，客服人员向记者解释，“用户还车时，如果此网点车位已满，就需去其他网点还车，如若停在此处，必须缴纳100元超停费用。”

问题：

附件是共享汽车的位置数据集，数据集中提供了时间，经纬度等位置信息，以及停车点上停放的车辆的数量和车辆表。请建立数学模型分析该城市的共享汽车使用分布情况，并且制定一个对企业最有利的共享汽车调度方案。
不多废话直接上
计算过程
第1步：初始化距离，其实指与D直接连接的点的距离。dis[c]代表D到C点的最短距离，因而初始dis[C]=3，dis[E]=4，dis[D]=0，其余为无穷大。设置集合S用来表示已经找到的最短路径。此时，S={D}。现在得到D到各点距离{D(0)，C(3)，E（4），F（），G（），B（），A()}，其中*代表未知数也可以说是无穷大，括号里面的数值代表D点到该点的最短距离。

第2步：不考虑集合S中的值，因为dis[C]=3，是当中距离最短的，所以此时更新S，S={D,C}。接着我们看与C连接的点，分别有B，E，F，已经在集合S中的不看，dis[C-B]=10，因而dis[B]=dis[C]+10=13，dis[F]=dis[C]+dis[C-F]=9，dis[E]=dis[C]+dis[C-E]=3+5=8>4(初始化时的dis[E]=4)不更新。此时{D(0)，C(3)，E（4），F（9），G（），B（13），A()}。

第3步：在第2步中，E点的值4最小，更新S={D，C，E}，此时看与E点直接连接的点，分别有F，G。dis[F]=dis[E]+dis[E-F]=4+2=6（比原来的值小，得到更新），dis[G]=dis[E]+dis[E-G]=4+8=12（更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(*)}。

第4步：在第3步中，F点的值6最小，更新S={D，C，E，F}，此时看与F点直接连接的点，分别有B，A，G。dis[B]=dis[F]+dis[F-B]=6+7=13，dis[A]=dis[F]+dis[F-A]=6+16=22，dis[G]=dis[F]+dis[F-G]=6+9=15>12（不更新）。此时{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第5步：在第4步中，G点的值12最小，更新S={D，C，E，F，G}，此时看与G点直接连接的点，只有A。dis[A]=dis[G]+dis[G-A]=12+14=26>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

第6步：在第5步中，B点的值13最小，更新S={D，C，E，F，G，B}，此时看与B点直接连接的点，只有A。dis[A]=dis[B]+dis[B-A]=13+12=25>22(不更新)。{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.
进群讨论即可

第6步：最后只剩下A值，直接进入集合S={D，C，E，F，G，B，A}，此时所有的点都已经遍历结束，得到最终结果{D(0)，C(3)，E（4），F（6），G（12），B（13），A(22)}.

设Di,j,k为从i到j的只以(1…k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1；
若最短路径不经过点k，则Di,j,k = Di,j,k-1。
因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

Floyd-Warshall算法的描述如下：
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
if (Di,k + Dk,j < Di,j) then
Di,j ← Di,k + Dk,j;
其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。