首页 > 代码库 > 算法8-7:最短路径接口
算法8-7:最短路径接口
最短路径问题就是给定一个图,这个图中的边是有方向和权重的。求s到t的最短路径。
最短路径问题其实分为很多种。按照起点和终点来分,可以分为:
从一个顶点到另一个顶点
从一个顶点到其他所有顶点
从所有顶点到所有顶点
按照边的权重来分可以分为:
非负权
任意权
欧几里德权
按照是否有环可以分为
无环最短路径
无负环最短路径
类的定义
在实现最短路径算法之前,需要先在程序中定义有向权重图。
有向权重边的定义如下:
public class DirectedEdge { private int v; private int w; private double weight; public DirectedEdge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; } public int from() { return v; } public int to() { return w; } public double weight() { return this.weight; } @Override public String toString() { return String.format("%s->%s[%s]", v, w, weight); } }
有向权重图的定义如下:
import java.util.LinkedList; public class EdgeWeightedDigraph { private int V; private LinkedList<DirectedEdge>[] adj; public EdgeWeightedDigraph(int V) { this.V = V; adj = new LinkedList[V]; for (int i = 0; i < V; i++) { adj[i] = new LinkedList<DirectedEdge>(); } } public void addEdge(DirectedEdge edge) { int v = edge.from(); adj[v].add(edge); } public Iterable<DirectedEdge> adj(int v) { return adj[v]; } public int V() { return V; } public int E() { int result = 0; for (LinkedList<DirectedEdge> e : adj) { result += e.size(); } return result; } @Override public String toString() { String result = ""; for (int i = 0; i < adj.length; i++) { result += i + ":"; for (DirectedEdge e : adj[i]) { result += String.format(" %s[%s]", e.to(), e.weight()); } } return result; } }
这样定义有向权重图的好处就是可以有自连接,可以实现顶点之间有多个连接。
最短路径算法类的接口如下:
public class SP { public double distTo(int v); public Iterable<DirectedEdge> pathTo(int v); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。