最短距离算法

最短距离算法"/>

最短距离算法

无权最短路径

无权图可以把每条路径的权看成是1，求解起来非常简单。这种图的求法一般用广度优先搜索，按层来处理顶点，和二叉树的层序遍历非常类似，如下：

<T extends Comparable<? Super T>>  void printTree(BinaryNode<T> t){LinkedList<T> list = new LinkedList<>();
List.offer(t);while(list.size()>0){T t = list.poll();System.println.out(t.element);if(t.left!=null) list.offer(t.left);If(t.right!=null)list.offer(t.right);}
}

可以看到，使用链表来保存节点之前把父节点已经打印处理完了，直到没有儿子为止。

那么无权图的伪代码可以仿照层序遍历来写：

void unweighted(Vertex s){Queue<Vertex> q = new Queue<Vertex>();for each Vertex v v.dist = INFINITY;s.dist = 0;
q.enqueue(s);while(!q.isEmpty())
{Vertex v = q.dequeue();for each Vertex w adjacent to vif(w.dist == INFINITY){w.dist = v.dist + 1;w.path = v;q.enqueue(w);}}
}

赋权最短路径

如果每条路径的长度不一样，那么求解起来要比无权的要复杂的多，这种情况一般采用Dijkstra算法，Dijkstra算法首先选择一个顶点s作为起点，然后计算出s的所有邻点到s的距离，选择权最短的那条路径的顶点，作为开始，同时标记这个顶点的距离为know的，一直循环到图中没有unknow的路径为止。

void dijkstra(Vertex s){for each Vertex v 
{v.dist = INFINITY;v.know = false;
}s.dist = 0 ;while(there is an unknow distance vertex)
{Vertex v = smallest unknow distance vertex;v.know = true;for each Vertex w adjacent to vif(!w.know){//从V到W花费的距离DistType cvw = cost of edge from v to w;if(v.dist + cvw < w.dist){//更新W的distdecrease(w.dist to v.dist + cvw);w.path = v;}}   }
}//打印路径
void printPath(Vertex v){if(v.path != null){printPath(v.path);System.out.print(“ to ”);}System.out.print(v);
}

具有负边值的图

如果点到点的路径有负值的话，Dijkstra算法就行不通了，比如下面的情况：





按照Dijkstra算法的走向是s->v->u，此时s->u的最短距离是4。而从s->q->u走法，u的距离为-6。所以在这种情况下就不合法了，一般对于有负值边的图的处理方式是将广度优先搜索算法和Dijkstra算法结合起来，如下：

void weightNegative(Vertex s){Queue<Vertex> q = new Queue<>();for each Vertex v v.dist = INFINITY;s.dist = 0;
q.enqueue(s);while(!q.isEmpty())
{Vertex v = q.dequeue();for each Vertex w adjacent to vif(v.dist + cvw < w.dist){w.dist = v.dist + cvw;w.path = v;if( w is not already in q)q.enqueue(w);}}
}

可以看到，通过计算最小距离入队的方式，来不停的改变各个顶点的距离，就不需要unknow这个属性了，但是却牺牲了大量的时间为代价。

资料

《数据结构与算法分析》