最短路径

到了与实际应用中最接近的模型了，加权有向图，本节最关注的问题就是：找到从一个顶点到另一个顶点到成本最小的路径。

为简化问题，样图都是强连通的（每个顶点从另外任意一个顶点都是可达的），可能有多条最短路径，我们只要找出其中一条即可。

重点是单点最短路径问题，给出起点s，计算的结果是一颗最短路径树（SPT），它包含了顶点s到所有可达的顶点的最短路径。

加权有向图的数据结构

加权有向边，基本上跟mst那节的edge类差不多，改了写名字而已。

class DirectedEdge {
  private v: number
  private w: number
  private weight: number

  constructor(v: number, w: number, weight: number) {
    this.v = v
    this.w = w
    this.weight = weight
  }

  public getWeight() {
    return this.weight
  }

  public from() {
    return this.v
  }

  public to() {
    return this.w
  }
}

加权有向图的数据结构，也和之前mst的图结构差不多，只是把Edge改成了DirectedEdge

class EdgeWightedGraph {
  private V: number
  private E: number
  private adj: DirectedEdge[][]

  constructor(data: TGraphData) {
    this.V = data.V
    this.E = 0
    this.adj = []

    data.edges.forEach(([v, w, weight]) => this.addEdge(new DirectedEdge(v, w, weight)))
  }

  public addEdge(e: DirectedEdge) {
    const from = e.from()
    const to = e.to()
    this.adj[from] = this.adj[from] || []
    this.adj[to] = this.adj[to] || []
    this.adj[from].push(e)
    this.E++
  }

  public adjOf(v: number) {
    return this.adj[v]
  }

  public getV() {
    return this.V
  }

  public getE() {
    return this.E
  }

  public getEdges() {
    return this.adj.flat();
  }
}

测试数据

const data: TGraphData = {
  V: 8,
  edges: [
    [4, 5, 0.35],
    [5, 4, 0.35],
    [4, 7, 0.37],
    [5, 7, 0.28],
    [7, 5, 0.28],
    [5, 1, 0.32],
    [0, 4, 0.38],
    [0, 2, 0.26],
    [7, 3, 0.39],
    [1, 3, 0.29],
    [2, 7, 0.34],
    [6, 2, 0.40],
    [3, 6, 0.52],
    [6, 0, 0.58],
    [6, 4, 0.93]
  ]
}

Dijkstra算法

暂时只考虑非负权重的情况。基本过程是从s出发，在遍历每一条边的过程中，不断更新distTo和edgeTo。

class DijkstraSP {
  private edgeTo: DirectedEdge[]  // edgeTo[w]表示指向w的权值最小的边
  private distTo: number[]  // distTo[w]从s到w的最小权值
  private pq: IndexMinPQ

  constructor(g: EdgeWightedGraph, s: number) {
    this.edgeTo = []
    this.distTo = []
    this.pq = new IndexMinPQ(g.getV())

    for (let v = 0; v < g.getV(); v++) {
      this.distTo[v] = Infinity
    }
    this.distTo[s] = 0

    this.pq.insert(s, 0)
    while (!this.pq.isEmpty()) {
      this.relax(g, this.pq.delMin())
    }
  }

  private relax(g: EdgeWightedGraph, v: number) {
    g.adjOf(v).forEach(e => {
      const w = e.to()
      if (this.distTo[w] > this.distTo[v] + e.getWeight()) {
        this.distTo[w] = this.distTo[v] + e.getWeight()
        this.edgeTo[w] = e
        if (this.pq.contains(w)) this.pq.change(w, this.distTo[w])
        else  this.pq.insert(w, this.distTo[w])
      }
    })
  }

  public hasPathTo(w: number) {
    return this.edgeTo[w] !== undefined;
  }

  public pathTo(w: number) {
    const path: DirectedEdge[] = []
    for (let v = w; this.edgeTo[v] !== undefined; v = this.edgeTo[v].from()) {
      path.unshift(this.edgeTo[v])
    }
    return path
  }

  public getDistTo(w: number) {
    return this.distTo[w]
  }
}

测试用例：

const main = () => {
  const g = new EdgeWightedGraph(data)
  const s = 0;
  const sp = new DijkstraSP(g, s)
  for (let t = 0; t < g.getV(); t++) {
    let str = `${s} to ${t} (${sp.getDistTo(t)}): `;
    if (sp.hasPathTo(t)) {
      sp.pathTo(t).forEach(e => {
        str += `${e.from()}->${e.to()} ${e.getWeight()} `
      })
    }
    console.log(str)
  }
}
/*
0 to 0 (0): 
0 to 1 (1.05): 0->4 0.38 4->5 0.35 5->1 0.32 
0 to 2 (0.26): 0->2 0.26 
0 to 3 (0.9900000000000001): 0->2 0.26 2->7 0.34 7->3 0.39 
0 to 4 (0.38): 0->4 0.38 
0 to 5 (0.73): 0->4 0.38 4->5 0.35 
0 to 6 (1.5100000000000002): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 
0 to 7 (0.6000000000000001): 0->2 0.26 2->7 0.34 
*/

在一副含有V个顶点和E条边的加权有向图中，使用Dijkstra算法计算根节点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比（最坏情况下）

无环加权有向图中的最短路径算法

接下来这个算法比Dijkstra算法更快，但是前提是无环。它的特点是：

• 能够在线性时间内解决单点最短路径问题
• 能够处理负权重的边
• 能够找出最长路径

与Dijkstra主要的不同就是根据图的拓扑排序顺序来进行relax操作

按照拓扑顺序放松顶点，就能够在和E+V成正比的时间内解决无环加权有向图的单点最短路径问题

拓扑排序需要的时间是与E+V成正比，之后会每条边会再遍历一次，每条边都只会被放松一次，因此算法总耗时与E+V成正比。对比Dijkstra起来，我感觉其实就是少了对优先队列操作的那些时间。

class AcyclicSP {
  private edgeTo: DirectedEdge[]
  private distTo: number[]

  constructor(g: EdgeWightedGraph, s: number) {
    this.edgeTo = []
    this.distTo = []
    for (let v = 0; v < g.getV(); v++) {
      this.distTo[v] = Infinity
    }
    this.distTo[s] = 0

    const top = new Topological(g)
    top.getOrder().forEach(v => {
      this.relax(g, v)
    })
  }
}

其余的relax等方法与Dijkstra中一样。

测试：

const data: TGraphData = {
  V: 8,
  edges: [
    [5, 4, 0.35],
    [4, 7, 0.37],
    [5, 7, 0.28],
    [5, 1, 0.32],
    [4, 0, 0.38],
    [0, 2, 0.26],
    [3, 7, 0.39],
    [1, 3, 0.29],
    [7, 2, 0.34],
    [6, 2, 0.40],
    [3, 6, 0.52],
    [6, 0, 0.58],
    [6, 4, 0.93]
  ]
}

const main = () => {
  const g = new EdgeWightedGraph(data)
  const s = 5;
  const sp = new AcyclicSP(g, s)
  for (let t = 0; t < g.getV(); t++) {
    let str = `${s} to ${t} (${sp.getDistTo(t)}): `;
    if (sp.hasPathTo(t)) {
      sp.pathTo(t).forEach(e => {
        str += `${e.from()}->${e.to()} ${e.getWeight()} `
      })
    }
    console.log(str)
  }
}

/*
5 to 0 (0.73): 5->4 0.35 4->0 0.38 
5 to 1 (0.32): 5->1 0.32 
5 to 2 (0.6200000000000001): 5->7 0.28 7->2 0.34 
5 to 3 (0.61): 5->1 0.32 1->3 0.29 
5 to 4 (0.35): 5->4 0.35 
5 to 5 (0): 
5 to 6 (1.13): 5->1 0.32 1->3 0.29 3->6 0.52 
5 to 7 (0.28): 5->7 0.28 
*/

因为图不是强连通，所以会有不可达的情况出现，这个时候v to w就是Infinity。

最长路径

如果要找最长路径就把图复制一份，并把复制的那份的边的权重都变成负的，然后再对复制后的图执行算法得到的就是最长路径了。

解决无环加权有向图中的最长路径问题所需的时间与E+V成正比

应用场景：优先级限制下的并行任务调度。给定一组需要完成的特定任务，以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何在若干**相同处理器上（数量不限）**安排任务并在最短的时间内完成所有任务。

之前讲到拓扑排序的时候用的例子默认是单个处理器，完成任务的总耗时就是所有任务所需要的总时间。现在假设有足够多的处理器并能够同时处理任意多的任务，那么就只受优先级的限制了。这个时候图的最长路径就是所有任务完成的最短时间了。

上图的解决方案就是这个调度问题的最优解，耗时最少，任务必须按照0, 9, 6, 8, 2的顺序完成，这个顺序叫做这个问题的关键路径。

解决这个这个问题之前，先要构造一个如下这样的图，关于具体是个咋样的图，不是很好描述，不如直接看代码来得更好理解。

由AcyclicSP修改而来，主要就是将图的权重变成负的，然后再进行relax操作。

class AcyclicLP {
  private edgeTo: DirectedEdge[]
  private distTo: number[]

  constructor(g: EdgeWightedGraph, s: number) {
    this.edgeTo = []
    this.distTo = []

    const ng = this.negativeGraph(g);
    for (let v = 0; v < ng.getV(); v++) {
      this.distTo[v] = Infinity
    }
    this.distTo[s] = 0

    const top = new Topological(ng)
    top.getOrder().forEach(v => {
      this.relax(ng, v)
    })
  }

  private negativeGraph(g: EdgeWightedGraph) {
    const edges: TEdge[] = []
    g.getEdges().forEach(e => {
      edges.push([e.from(), e.to(), -e.getWeight()])
    })
    const data: TGraphData = {
      V: g.getV(),
      edges,
    }
    return new EdgeWightedGraph(data)
  }

  private relax(g: EdgeWightedGraph, v: number) {
    g.adjOf(v).forEach(e => {
      const w = e.to()
      if (this.distTo[w] > this.distTo[v] + e.getWeight()) {
        this.distTo[w] = this.distTo[v] + e.getWeight()
        this.edgeTo[w] = e
      }
    })
  }

  public hasPathTo(w: number) {
    return this.edgeTo[w] !== undefined;
  }

  public pathTo(w: number) {
    const path: DirectedEdge[] = []
    for (let v = w; this.edgeTo[v] !== undefined; v = this.edgeTo[v].from()) {
      path.unshift(this.edgeTo[v])
    }
    return path
  }

  public getDistTo(w: number) {
    return -this.distTo[w]
  }
}

测试用例：

const data: TTask = {
  V: 10,
  tasks: [
    [41, 1, 7, 9],
    [51, 2],
    [50],
    [36],
    [38],
    [45],
    [21, 3, 8],
    [32, 3, 8],
    [32, 2],
    [29, 4, 6]
  ]
}

const main = () => {
  const n = data.V
  const V = 2 * n + 2
  const s = n * 2, t = 2 * n + 1
  const edges: TEdge[] = []
  for (let i = 0; i < data.tasks.length; i++) {
    const task = data.tasks[i]
    const [weight, ...next] = task
    edges.push([i, i + n, weight])
    edges.push([s, i, 0])
    edges.push([i + n, t, 0])

    for (let j = 0; j < next.length; j++) {
      const successor = next[j]
      edges.push([i + n, successor, 0])
    }
  }
  const graphData: TGraphData = {
    V,
    edges,
  }
  const g = new EdgeWightedGraph(graphData)
  const lp = new AcyclicLP(g, s)
  console.log('Start times:')
  for (let i = 0; i < n; i++) {
    console.log(`${i}: ${lp.getDistTo(i)}`)
  }
  console.log(`Finish time: ${lp.getDistTo(t)}`)
  
  const path: number[] = []
  lp.pathTo(t).forEach(e => {
    const from = e.from()
    if (from < n && !path.includes(from)) {
      path.push(from)
    }
  })
  console.log(`path: ${path.join(', ')}`)
}
/*
Start times:
0: 0
1: 41
2: 123
3: 91
4: 70
5: 0
6: 70
7: 41
8: 91
9: 41
Finish time: 173
path: 0, 9, 6, 8, 2
*/

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

所谓“一般”指的就是当存在负权重或者环的时候。负权重环带来的问题就是最短路径不唯一，如下图中，只有5->4是负的，且环4->7->5->4的总权重为-0.01，那么我们只要围着这个环兜圈子就能得到权重更短的路径。

当且仅当加权有向图中至少存在一条从s到v到有向路径且所有从s到v的有向路径上任意顶点都不存在于任何负权重环中时，s到v到最短路径才存在。

尽管在含有负有向环的图中找最短路径是没有意义的，但是在实际应用中如何找到负有向环仍然是必要的，因为这或许是一些粗心造成的这种情况，为了可以修正图的数据，检测并找到环仍然是有意义的。

基于队列的Bellman-Ford算法

根据经验知道在任意一轮中许多边的放松都不会成功：只有上一轮中distTo[]值发生变化的顶点指出的边才能够改变其他distTo[]元素的值。为了记录这样的顶点，使用了FIFO队列。

因为要检测并找到负有向环，所以这里实现了一个叫做findNegativeCycle的方法，实际使用的算法其实就是之前提到过有向环的检测算法，这里做了的不过是将目前添加到路径树中的边构建一个图来用检测。

class BellmanFordSP {
  private distTo: number[] = []
  private edgeTo: DirectedEdge[] = []
  private onQ: boolean[] = []
  private queue: number[] = []
  private cost: number = 0
  private cycle: number[] =[]

  constructor(g: EdgeWightedGraph, s: number) {
    for (let v = 0; v < g.getV(); v++) {
      this.distTo[v] = Infinity
    }
    this.distTo[s] = 0
    this.queue.push(s)
    this.onQ[s] = true

    while (this.queue.length !== 0 && !this.hasNegativeCycle()) {
      const v = this.queue.shift() as number // queue.dequeue(); 这个shift是返回number|undefined，不用as会报错
      this.onQ[v] = false
      this.relax(g, v)
    }
  }

  private relax(g: EdgeWightedGraph, v: number) {
    g.adjOf(v).forEach(e => {
      const w = e.to()
      if (this.distTo[w] > this.distTo[v] + e.getWeight()) {
        this.distTo[w] = this.distTo[v] + e.getWeight()
        this.edgeTo[w] = e
        if (!this.onQ[w]) {
          this.queue.push(w)
          this.onQ[w] = true
        }
      }
      // 这个地方书上应该是写错了，写成了cost++，特意查了他们官网的代码是++cost
      if (++this.cost % g.getV() === 0) {  
        this.findNegativeCycle()
        if (this.hasNegativeCycle()) return
      }
    })
  }

  public negativeCycle() {
    return this.cycle
  }

  public hasNegativeCycle() {
    return this.cycle.length !== 0
  }

  public findNegativeCycle() {
    const v = this.edgeTo.length
    const edges: TEdge[] = []
    this.edgeTo.forEach(e => {
      if (e) {
        edges.push([e.from(), e.to(), e.getWeight()])
      }
    })
    const cycleGraph: TGraphData =  {
      V: v,
      edges
    }

    const spt = new EdgeWightedGraph(cycleGraph)
    const cyclefinder = new DirectedCycle(spt)

    this.cycle = cyclefinder.getCycle()
  }
}

测试无负权重环，但含有负权重边的图：(虚线为负权重边)

const data: TGraphData = {
  V: 8,
  edges: [
    [4, 5, 0.35],
    [5, 4, 0.35],
    [4, 7, 0.37],
    [5, 7, 0.28],
    [7, 5, 0.28],
    [5, 1, 0.32],
    [0, 4, 0.38],
    [0, 2, 0.26],
    [7, 3, 0.39],
    [1, 3, 0.29],
    [2, 7, 0.34],
    [6, 2, -1.2],
    [3, 6, 0.52],
    [6, 0, -1.4],
    [6, 4, -1.25]
  ]
}

/*
0 to 0 (0): 
0 to 1 (0.9300000000000002): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25 4->5 0.35 5->1 0.32 
0 to 2 (0.26): 0->2 0.26 
0 to 3 (0.9900000000000001): 0->2 0.26 2->7 0.34 7->3 0.39 
0 to 4 (0.26000000000000023): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25 
0 to 5 (0.6100000000000002): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25 4->5 0.35 
0 to 6 (1.5100000000000002): 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 
0 to 7 (0.6000000000000001): 0->2 0.26 2->7 0.34
*/

测试含负权重环的图：

const data1: TGraphData = {
  V: 8,
  edges: [
    [4, 5, 0.35],
    [5, 4, -0.66],
    [4, 7, 0.37],
    [5, 7, 0.28],
    [7, 5, 0.28],
    [5, 1, 0.32],
    [0, 4, 0.38],
    [0, 2, 0.26],
    [7, 3, 0.39],
    [1, 3, 0.29],
    [2, 7, 0.34],
    [6, 2, 0.4],
    [3, 6, 0.52],
    [6, 0, 0.58],
    [6, 4, 0.93]
  ]
}
/*
cycle:
4->5 0.35
5->4 -0.66
*/

套汇

有如下汇率数据，在不考虑其他手续费之类的费用都情况下，如果只是单纯的1000 USD换GBP的，然后再由GBP换USD，最后手上的USD是不会多也不会少，还是1000。但是如果1000 USD先换EUR再换GBP，再用GBP换回USD手上就有1000*0.741*0.888*1.521=1000.83USD，赚了0.83。这就是套汇。

套汇问题等价于加权有向图中的负权重环的检测问题

显而易见的是，各种货币就对应图中顶点，而汇率就对应有向路径的权重。那么当环中权重之积大于1的时候，这个时候就是获利的，而权重之积w1w2...wk>1等价于ln(w1w2...wk)>0等价于-ln(w1)-ln(w2)...-ln(wk)<0，因此将所有权重转化成负对数，然后再找到图中的负权重环即可。

const data: TGraphData = {
  V: 5,
  edges: [
    [0, 1, 0.741],
    [0, 2, 0.657],
    [0, 3, 1.061],
    [0, 4, 1.005],
    [1, 0, 1.349],
    [1, 2, 0.888],
    [1, 3, 1.433],
    [2, 0, 1.521],
    [2, 1, 1.126],
    [2, 3, 1.614],
    [2, 4, 1.538],
    [3, 0, 0.942],
    [3, 1, 0.698],
    [3, 2, 0.619],
    [3, 4, 0.953],
    [4, 1, 0.732],
    [4, 2, 0.650],
    [4, 3, 1.049],
  ]
}

const names = ['USD', 'EUR', 'GBP', 'CHF', 'CAD']

const main = () => {
  const lnEdges = data.edges.map(([s, t, w]) => [s, t, -Math.log(w)] as TEdge)
  data.edges = lnEdges
  const g = new EdgeWightedGraph(data)
  const spt = new BellmanFordSP(g, 0)
  if (spt.hasNegativeCycle()) {
    let stake = 1000
    const cycle = spt.negativeCycle()
    cycle.forEach(e => {
      let str = `${stake} ${names[e.from()]} = `
      stake *= Math.exp(-e.getWeight())
      str += `${stake} ${names[e.to()]}`
      console.log(str)
    })   
  }
}

/*
1000 USD = 741 EUR
741 EUR = 658.008 GBP
658.008 GBP = 1000.830168 USD
*/

可能有多个负权重环，书上说目前没有已知的最佳套汇高效算法。这里依照数据的顺序不同，relax顺序就会不同，可能产生不同的结果，比如这里和书上的结果就不一样，书上是USD->EUR->CAD->USD这个环。

总结

本节代码：https://github.com/Yuijam/algorithms-note/tree/main/graph/spt