相关链接
783. 最小危险值路径
数据结构–最小生成树详解
最短路径算法之 Floyd
在线测试
1. 点击右边的测试数据按钮，可以切换数据
2. 点击右边的最小生成树，可以切换是否开启这功能
3. 点击右边的操作模式
* 拖动节点： 可以拖动节点，默认都可以
* 设置起始点： 选中该模式，再点击节点，可以将该节点设置为最短寻路起始点。节点下标Start
* 设置结束点： 选中该模式，再点击节点，可以将该节点设置为最短寻结束点。节点下标End
寻得的路线为绿色连线，红色表示该路线中成本最大的值
4. 修改数据
(1) 先点击“导出数据按钮”，会在页面下方输出图形json数据
(2) 编辑数据，点提交就可以修改了。只需要修改属性 x(起点), y(目标点), w(成本)
Prim.ts
namespace ihaiu
{
/** 作为记录边的信息，这些边都是达到end的所有边中，权重最小的那个 */
export class PrimAssis
{
// 边的终点
start: number = 0;
// 边的起点
end: number = 0;
// 边的权重
weight: number = 0;
}
/** 最小生成树之Prim普里姆算法 */
export class Prim
{
// 成本矩阵
arcs: number[][];
// 计算结果
result: GraphData;
constructor()
{
}
/** 获取路径成本 */
public getArcs(from: number, to: number): number
{
return this.arcs[from][to];
}
/** 是否有连接线 */
public hasEdge(from: number, to: number): boolean
{
let arc = this.getArcs(from, to);
return arc != Number.MAX_VALUE && arc != 0;
}
public calculationByGraphData(g: GraphData, beginIndex: number = 0):GraphData
{
g.check();
let g2 = this.calculation(
g.nodeNum,
g.edegeNum,
g.x,
g.y,
g.w,
beginIndex
);
g2.nodeNum = g.nodeNum;
g2.nodes = g.nodes;
return g2;
}
/** 计算寻路 */
public calculation(nodeNum: number, edegeNum: number, x: number[], y: number[], w: number[], beginIndex: number = 0):GraphData
{
// 结果图
let result: GraphData = new GraphData().init();
// 成本矩阵
let arcs: number[][] = [];
// 初始化矩阵值
for(let u = 0; u < nodeNum; u ++)
{
arcs[u] = [];
for(let v = 0; v < nodeNum; v ++)
{
arcs[u][v] = Number.MAX_VALUE;
}
}
// 输入边
for(let i = 0; i < x.length; i ++)
{
let u = x[i];
let v = y[i];
arcs[u][v] = w[i];
arcs[v][u] = w[i];
}
//closeEdge这个数组记录到达某个顶点的各个边中的权重最大的那个边
let closeEdges: PrimAssis[] = [];
for(let i = 0; i < nodeNum; i ++)
{
closeEdges.push(new PrimAssis());
}
//进行closeEdge的初始化，更加开始起点进行初始化
for(let i = 0; i < nodeNum; i ++)
{
if(i != beginIndex)
{
let edge = closeEdges[i];
edge.start = beginIndex;
edge.end = i;
edge.weight = arcs[beginIndex][i];
}
}
//把起点的closeEdge中的值设置为-1，代表已经加入到集合U了
closeEdges[beginIndex].weight = -1;
//访问剩下的顶点，并加入依次加入到集合U
for(let i = 1; i< nodeNum; i ++)
{
let minWeight = Number.MAX_VALUE;
let minIndex = 0;
//寻找数组close_edge中权重最小的那个边
for(let k = 0; k < nodeNum; k ++)
{
if(closeEdges[k].weight != -1)
{
if(closeEdges[k].weight < minWeight)
{
minWeight = closeEdges[k].weight;
minIndex = k;
}
}
}
let minEdge = closeEdges[minIndex];
//将权重最小的那条边的终点也加入到集合U
minEdge.weight = -1;
//输出对应的边的信息
result.addEdge(
minEdge.start,
minEdge.end,
arcs[minEdge.start][minEdge.end]
);
//更新我们的close_edge数组。
for (let k = 0; k < nodeNum; k++) {
let edge = closeEdges[k];
if (arcs[minEdge.end][k] < edge.weight)
{
edge.weight = arcs[minEdge.end][k];
edge.start = minEdge.end;
edge.end = k;
}
}
}
this.arcs = arcs;
this.result = result;
return result;
}
}
}
GraphData.ts
namespace ihaiu
{
/**
* 图形数据
*/
export class GraphData
{
// 边--from
x: number[];
// 边--to
y: number[];
// 边--危险值
w: number[];
// 节点数量
nodeNum = 0;
// 边数
edegeNum = 0;
// 节点
nodes: Node[] = [];
public init(): GraphData
{
this.x = [];
this.y = [];
this.w = [];
return this;
}
// 添加边
public addEdge(x: number, y:number, w: number): GraphData
{
this.x.push(x);
this.y.push(y);
this.w.push(w);
return this;
}
public check()
{
this.checkNodeNum();
this.edegeNum = this.x.length;
if(this.nodes != null && this.nodes.length >= this.nodeNum)
{
return;
}
let list: Node[] = [];
for(let i = 0; i < this.nodeNum; i ++)
{
let node : Node;
if(i < this.nodes.length )
{
node = this.nodes[i];
}
else
{
node = new Node();
node.pos.x = Math.floor( Math.random() * 200 + 50 ) ;
node.pos.y = Math.floor( Math.random() * 200 + 50 );
}
node.index = i;
list.push(node);
}
this.nodes = list;
}
// 矫正顶点数量
public checkNodeNum()
{
let x = this.x;
let y = this.y;
let num = 0;
for(let i = 0; i < x.length; i ++)
{
num = Math.max(x[i], num);
num = Math.max(y[i], num);
}
this.nodeNum = Math.max(num + 1, this.nodeNum);
}
static parse(json:string)
{
let g = new GraphData();
try
{
let o = JSON.parse(json);
g.edegeNum = o.edegeNum;
g.nodeNum = o.nodeNum;
g.x = o.x;
g.y = o.y;
g.w = o.w;
let list: Node[] = [];
for(let i = 0; i < o.nodes.length; i ++)
{
let item = o.nodes[i];
let node : Node = new Node();
node.index = item.index;
node.pos.x = item.pos.x;
node.pos.y = item.pos.y;
list.push(node);
}
g.nodes = list;
}
catch (error)
{
alert("解析json数据错误：" + error);
}
return g;
}
}
}
Node.ts
namespace ihaiu
{
export class NodeState
{
static Normal = 0;
static Disable = 1;
static Start = 2;
static End = 3;
static Greend = 4;
}
export class LineState
{
static Normal = 0;
static Disable = 1;
static Green = 2;
static GreenMax = 3;
}
/**
* 节点
*/
export class Node
{
// 节点索引
index: number;
// 坐标
pos: Point = new Point();
// 子节点
// childes: Node[] = [];
}
}
Point.ts
namespace ihaiu
{
/**
* 路径点
*/
export class Point
{
x: number = 0;
y: number = 0;
/** 获取到目标点距离 */
public getDistance(to: Point): number
{
let dx = to.x - this.x;
let dy = to.y - this.y;
return Math.sqrt(dx * dx + dy * dy);
}
/** 获取到目标点弧度 */
public getRadian(to: Point) : number
{
let dx = to.x - this.x;
let dy = to.y - this.y;
return Math.atan2(dy, dx);
}
/** 获取到目标点角度 */
public getAngle(to: Point) : number
{
return this.getRadian(to) * 180 / Math.PI ;
}
/** 获取中心点 */
public static center(a: Point, b: Point): Point
{
let p = new Point();
p.x = a.x + (b.x - a.x) * 0.5;
p.y = a.y + (b.y - a.y) * 0.5;
return p;
}
/** 获取相对A中心点 */
public static centerRelative(a: Point, b: Point): Point
{
let p = new Point();
p.x = (b.x - a.x) * 0.5;
p.y = (b.y - a.y) * 0.5;
return p;
}
}
}