最短路径(算法第四版)(C#)

最短路径

• 最短路径的性质
• 有向加权图的数据结构
• 最短路径的API
• 最短路径的基础
• Relaxation(松弛)
• 最短路径的最优性条件

• Bellman-Ford算法

最短路径的性质

1. 路径是有向的
2. 不需要所有边都可达
3. 负权重会使问题变得更复杂
4. 最短路径不是唯一的

这里讨论的是单点最短路径，即找出从一个起点到所有可达顶点的最短路径构成的最短路径树。

有向加权图的数据结构

有向边的结构比无向边简单，有确定的起点和终点
有向边的结构：

public class DirectEdge{private int v;  //起点private int w;  //终点private double weight;public DirectEdge(int form, int to, double weight){this.v = form;this.w = to;this.weight = weight;}public int Form => v;public int To => w;public double Weight => weight;}

加权有向图的结构：

//加权有向图public class EdgeWeightedDigraph{private int v;private List<DirectEdge>[] _adj; //邻接表private int e;public EdgeWeightedDigraph(string path){string line;System.IO.StreamReader sr = new System.IO.StreamReader(path);v = Convert.ToInt32(sr.ReadLine());e = 0;_adj = new List<DirectEdge>[v];for (int i = 0; i < v; i++) { _adj[i] = new List<DirectEdge>(); }while ((line = sr.ReadLine()) != null){string[] str = line.Split(\' \');int a = Convert.ToInt32(str[0]);int b = Convert.ToInt32(str[1]);float w = (float)Convert.ToDouble(str[2]);AddEdge(new DirectEdge(a, b, w));}}public EdgeWeightedDigraph(int v){_adj = new List<DirectEdge>[v];for (int i = 0; i < v; i++){_adj[i] = new List<DirectEdge>();}this.v = v;e = 0;}public void AddEdge(DirectEdge edge){_adj[edge.Form].Add(edge);e++;}public int V => v;public int E => e;public List<DirectEdge> Adj(int v){return _adj[v];}//将加权有向图转换为有向图，后面使用拓扑排序会用到public Digraph ToDigraph(){Digraph g= new Digraph(v);for (int i = 0; i < _adj.Length; i++){foreach (DirectEdge e in _adj[i]){g.AddEdge(e.Form, e.To);}}return g;}}

最短路径的API

public class SPSP(EdgeWeightedDigraph G,int s)  //构造函数double DistTo(int v)             //s到v的距离，不存在时为无穷大bool HasPathTo(int v)            //是否可达DirectEdge[] PathTo(int v)

最短路径的基础

Relaxation(松弛)

初始化时将出起点以外的distTo都设置为Double.maxValue。Relax()就是比较记录中的距离(distTo[i]的值)和现在路径的距离(distTo[i]+edge.weight)，如果当前的值较小则更新数据。松弛也可以用于边的松弛：参数为有向边，一次仅松弛一条边，和节点的松弛：松弛节点的邻接表。

最短路径的最优性条件

对从v到w的任意一条边e，有distTo[w]<=distTo[v]+e.weight
判断路径是否为最短路径的全局条件和放松一条边的区部最优性是等价的。 如果你从起点开始，那么你所得到的路径全都满足松弛的条件，而反过来从一个已知的最短路径来看，这个最短路径的每一个结点也必须满足松弛的条件(感觉还是有点说不清楚?)

Dijkatra算法

适用范围： 权重为正的加权有向图。
思路： 类似于Prim算法（每次在队列中添加一个权最小的边到最小生成树中），初始将除起点以外的边的distTo都设置为最大。然后将distTo更小的点加入最小路径并放松该结点。
时间： 与ElogV成正比
空间： 与V成正比
源代码：

/// <summary>/// 求得正权重加权有向图的最短路径/// </summary>public class DijkstraSP{private DirectEdge[] edgeTo;private double[] distTo;private IndexMinPQ<double> pq;public DijkstraSP(int v, EdgeWeightedDigraph g){edgeTo = new DirectEdge[g.V];distTo = new double[g.V];pq = new IndexMinPQ<double>(g.V);for (int i = 0; i < g.V; i++)distTo[i] = Double.MaxValue;distTo[v] = 0;pq.Insert(v, 0);while (!pq.IsEmpty()){Relax(g, pq.DeleteMin());}}/// <summary>/// 松弛边，选择权更小的路径/// </summary>private void Relax(EdgeWeightedDigraph g,int v){foreach (DirectEdge edge in g.Adj(v)){int w = edge.To;if (distTo[v] + edge.Weight < distTo[w]){distTo[w] = distTo[v] + edge.Weight;edgeTo[w] = edge;if (pq.Contains(w)) pq.Change(w, distTo[w]);else pq.Insert(w, distTo[w]);}}}public double DistTo(int v){return distTo[v];}public bool HasPathTo(int v){return distTo[v] < Double.MaxValue;}public DirectEdge[] PathTo(int v){List<DirectEdge> edges = new List<DirectEdge>();edges.Add(edgeTo[v]);int w = v;while (edgeTo[w] != null){w = edgeTo[w].Form;edges.Add(edgeTo[w]);}return edges.ToArray();}}

处理无环加权有向图的最短路径

特点：

1. 能在线性时间处理单点最短路径问题
2. 能处理负权重的边
3. 能解决相关问题，例如找到最长路径

思路： 按照拓扑排序的顺序放松顶点，假设有一个图：a->b->c->d，那么按这个顺序放松，任意两个点都满足最优性条件，因为当点v被放松后，distTo[v]不会在发生变化，因为按拓扑排序放松，不会再处理指向v的边，所以到所有可达点都加入后，最优性条件成立。
源代码：

public class AcyclicSP{private DirectEdge[] edgeTo;private double[] distTo;public AcyclicSP(EdgeWeightedDigraph g){edgeTo = new DirectEdge[g.V];distTo = new double[g.V];for (int i = 0; i < g.V; i++) distTo[i] = Double.MaxValue;Topological topological = new Topological(g.ToDigraph());distTo[topological.Order[0]] = 0; //起点dist为0foreach (int v in topological.Order){Relax(g, v);}}/// <summary>/// 松弛顶点/// </summary>private void Relax(EdgeWeightedDigraph g, int v){foreach (DirectEdge edge in g.Adj(v)){int w = edge.To;if (distTo[v] + edge.Weight < distTo[w]){distTo[w] = distTo[v] + edge.Weight;edgeTo[w] = edge;}}}//同Dijkatrapublic double DistTo(int v){}public bool HasPathTo(int v){}public DirectEdge[] PathTo(int v){}}

一般加权有向图的最短路径

遇到的问题

1. 负权重可能会使我们为了经过负权重绕弯，或者在遍历图后，有结点经过一条负权重的边后还能使路径变短
2. 负权重环绕负权重环走可以使路径变得任意小

解决负权重环的问题：如果某个结点可达，但路径上有一个结点属于负权重环，则将该路径设置为负无穷

Bellman-Ford算法

在有V个结点的图中，取s为起点，将distTo[s]设置为0，其他distTo[]设置为无穷大。然后以任意顺序放松所有边，重复V轮。需要事件EV。
可以通过队列改进Bellman-Ford算法：因为只有在上一轮中distTo的值发生的顶点指出的边才能改变其他distTo的值。所以可以使用一个队列记录distTo改变的值，每次将一个结点出队后放松他指出的边。
负权重环的检测：
使用relax的次数大于结点数时，说明已经开始绕负权重环转圈了。
源代码：

public class BellmanFordSP{private Queue<int> queue;private double[] distTo;private DirectEdge[] edgeTo;private bool[] onQueue; //结点是否已经入队，防止重复入队。private int cost; //Relax调用次数private int[] cycle; //是否有负权重环public BellmanFordSP(EdgeWeightedDigraph g, int s){queue = new Queue<int>();distTo = new double[g.V];edgeTo = new DirectEdge[g.V];onQueue = new bool[g.V];for (int i = 0; i < distTo.Length; i++){distTo[i] = Double.MaxValue;}distTo[s] = 0;queue.Enqueue(s);onQueue[s] = true;while (!HasNegativeCycle && queue.Count > 0){int v = queue.Dequeue();onQueue[v] = false;Relax(g, v);}}private void Relax(EdgeWeightedDigraph g, int v){foreach (DirectEdge e in g.Adj(v)){int w = e.To;if (distTo[w] > distTo[v] + e.Weight){distTo[w] = distTo[v] + e.Weight;edgeTo[w] = e;if (!onQueue[w]){queue.Enqueue(w);onQueue[w] = true;}}if (cost++ % g.V == 0) FindNegativeCycle();}}/// <summary>/// 找出负权重环/// </summary>private void FindNegativeCycle(){int v = edgeTo.Length;EdgeWeightedDigraph spt = new EdgeWeightedDigraph(v);for (int i = 0; i < v; i++)if (edgeTo[i] != null)spt.AddEdge(edgeTo[i]);//书上用的一个定制的类，我没有找到，就用的有向环代替的DirectCycle directCycle = new DirectCycle(spt.ToDigraph());cycle = directCycle.Cycle;}public bool HasNegativeCycle => cycle != null;public int[] NegativeCycle => cycle;public double DistTo(int v){return distTo[v];}public bool HasPathTo(int v){return distTo[v] < Double.MaxValue;}public DirectEdge[] PathTo(int v){List<DirectEdge> edges = new List<DirectEdge>();edges.Add(edgeTo[v]);int w = v;while (edgeTo[w] != null){w = edgeTo[w].Form;edges.Add(edgeTo[w]);}return edges.ToArray();}}