王者编程大赛之五最短路径

　　关注公众号后端搬运工《王者编程大赛之五最短路径》
　　外卖平台为了让骑手能在一天里送出更多的外卖，需要不断的优化从商家A到用户G的路径或者商家B到用户E的路径及距离。
　　请写出一种算法给你任意图中两点，计算出两点之间的最短距离。注：ABCDEFGH都可能是商家或者用户，点与点之间是距离。
　　解题思路
　　该题是求解无向图单源点的最短路径，经常采用Dijkstra算法求解，是按路径长度递增的次序产生最短路径。算法理论
　　Dijkstra算法是运用了最短路径的最优子结构性质，最优子结构性质描述为：
　　P（i，j）｛Vi，。。。，Vk，。。。Vs，Vj｝是从顶点i到j的最短路径，顶点k和s是这条路径上的一个中间顶点，那么P（k，s）必定也是从k到s的最短路径。
　　由于P（i，j）｛Vi，。。。，Vk，。。。Vs，Vj｝是从顶点i到j的最短路径，则有P（i，j）P（i，k）P（k，s）P（k，j）。若P（k，s）不是从顶点k到s的最短路径，那么必定存在另一条从顶点k到s的最短路径P’（k，s），故P’（i，j）P（i，k）P’（k，s）P（k，j）P（i，j），与题目相矛盾，因此P（k，s）是从顶点k到s的最短路径。
　　根据最短路径的最优子结构性质，Dijkstra提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点Vo，首先选择其直接相邻的顶点中最短路径的顶点Vi，那么可得从Vo到Vi顶点的最短距离D〔j〕min（D〔j〕，D〔j〕matrix〔i，j〕）（matrix〔i，j〕）为从顶点Vi到Vj的距离）。
　　假设存在图G｛V，E｝，V为所有顶点集合，源顶点为Vo，U｛Vo｝表示求得终点路径的集合，D〔i〕为顶点Vo到Vj的最短距离，P〔i〕为顶点Vo到Vj最短路径上的顶点。
　　算法描述为：
　　1）从VU中选择使D〔i〕值最小的顶点Vi，将Vi加入U中；
　　2）更新Vi与任一顶点Vj的最短距离，即D〔j〕min（D〔j〕，D〔j〕matrix〔i，j〕）；
　　3）直到UV，便求得从顶点Vo到图中任一一点的最短路径；
　　例如，求CG最短路径，算法过程可图示为：
　　源顶点VoC，顶点与索引关系为AH07，初始时：U｛false，false，false，false，false，false，false，false｝D｛INF，INF，0，INF，INF，INF，INF，INF｝P｛｛｝，｛｝，｛C｝，｛｝，｛｝，｛｝，｛｝，｛｝｝
　　将顶点C包含至U中：U｛false，false，true，false，false，false，false，false｝
　　更新顶点C至任一节点的距离：D｛6，9，0，11，INF，INF，INF，INF｝P｛｛C，A｝，｛C，B｝，｛C｝，｛C，D｝，｛｝，｛｝，｛｝，｛｝｝
　　再选择不在U中的最短路径顶点A，则将A包含至U中：U｛true，false，true，false，false，false，false，false｝
　　更新顶点A至任一节点的距离：D｛6，9，0，11，INF，25，INF，INF｝P｛｛C，A｝，｛C，B｝，｛C｝，｛C，D｝，｛｝，｛C，A，F｝，｛｝，｛｝｝
　　继续选择不在U中的最短路径顶点B，则将B包含至U中：U｛true，true，true，false，false，false，false，false｝
　　更新顶点B至任一节点的距离：D｛6，9，0，11，16，25，INF，INF｝P｛｛C，A｝，｛C，B｝，｛C｝，｛C，D｝，｛C，B，E｝，｛C，A，F｝，｛｝，｛｝｝
　　以此类推，直到遍历结束：U｛true，true，true，true，true，true，true，true｝D｛6，9，0，11，16，21，33，16｝P｛｛C，A｝，｛C，B｝，｛C｝，｛C，D｝，｛C，B，E｝，｛C，B，E，F｝，｛C，B，E，F，G｝，｛C，D，H｝｝
　　因此，CG的最短距离为33，最短路径为CBEFG。编码实现
　　实现的代码如下，并将一一详细说明。define（MAX，9999999999）；classPath｛图对应索引数组publicindexMatrixarray（）；顶点与索引映射关系publicindexMaparray（）；publicstartPoint；publicendPoint；publiclen0；最短距离publicDarray（）；已寻找集合publicUarray（）；最短路径publicParray（）；publicfunctionconstruct（arraymatrix，startPoint，endPoint）｛thisindexMaparraykeys（matrix）；thislencount（matrix）；arraywalk（matrix，function（value）｛valuearrayvalues（value）；｝）；thisindexMatrixarrayvalues（matrix）；thisstartPointarraysearch（startPoint，thisindexMap）；thisendPointarraysearch（endPoint，thisindexMap）；thisinit（）；｝publicfunctioninit（）｛for（i0；ithislen；i）｛初始化距离thisD〔i〕thisindexMatrix〔thisstartPoint〕〔i〕0？thisindexMatrix〔thisstartPoint〕〔i〕：MAX；thisP〔i〕array（）；初始化已寻找集合if（i！thisstartPoint）｛arraypush（thisP〔i〕，i）；thisU〔i〕false；｝else｛thisU〔i〕true；｝｝｝publicfunctiongetDistance（）｛returnthisD〔thisendPoint〕；｝publicfunctiongetPath（）｛paththisP〔thisendPoint〕；arrayunshift（path，thisstartPoint）；foreach（pathasvalue）｛valuethisindexMap〔value〕；｝returnpath；｝｝
　　Dijkstra算法求解：publicfunctiondijkstra（）｛for（l1；lthislen；l）｛minMAX；查找距离源点最近的节点｛v｝vthisstartPoint；for（i0；ithislen；i）｛if（！thisU〔i〕thisD〔i〕min）｛minthisD〔i〕；vi；｝｝thisU〔v〕true；更新最短路径for（i0；ithislen；i）｛if（！thisU〔i〕（minthisindexMatrix〔v〕〔i〕thisD〔i〕））｛thisD〔i〕minthisindexMatrix〔v〕〔i〕；thisP〔i〕arraymerge（thisP〔v〕，array（i））；｝｝｝｝
　　接收标准输入处理并输出结果：图matrixarray（Aarray（AMAX，B15，C6，DMAX，EMAX，F25，GMAX，HMAX），Barray（A15，BMAX，C9，DMAX，E7，FMAX，GMAX，HMAX），Carray（AMAX，B9，CMAX，D11，EMAX，FMAX，GMAX，HMAX），Darray（AMAX，BMAX，C11，DMAX，E12，FMAX，GMAX，H5），Earray（AMAX，B7，C6，D12，EMAX，F5，GMAX，H7），Farray（A25，BMAX，C6，DMAX，E5，FMAX，G12，HMAX），Garray（AMAX，BMAX，CMAX，DMAX，EMAX，F12，GMAX，H17），Harray（AMAX，BMAX，CMAX，D5，E7，F25，G17，HMAX），）；CGwhile（！inputtrim（fgets（STDIN），r〔〕））；pathnewPath（matrix，input｛0｝，input｛1｝）；pathdijkstra（）；echopathgetDistance（），，implode（，pathgetPath（）），PHPEOL；总结
　　本问题是求无向图源点的最短路径，时间复杂度为O（nn），若求解有向图源点的最短路径，只需将相邻顶点的逆向路径置为，即修改初始图的矩阵。不得不说的是，比求单源点最短路径更加复杂的求某一对顶点的最短路径问题，也可以以每一个顶点为源点使用Dijkstra算法求解，但是有更加简洁的Floyd算法。