iisp-ts-common/src/dijkstra.utils.ts

export class Dijkstra {
	private static MaxSize = 1000;
	/** 从某一源点出发，找到到某一结点的最短路径
	 * @param graph  图数据，它是一个二维矩阵，记录每两个点之间的距离
	 * @param start 起始节点索引号
	 * @param end 终点节点索引号
	 * @param path 数组，用于返回start到end顶点之间的路径
	 * @return 数组，从start到每个点之间的距离
	 */
	public static getShortedPath(graph: number[][], start: number, end: number, path: number[]): number {
		let length = graph.length;
		let s = new Array<boolean>(length); // 表示找到起始结点与当前结点间的最短路径
		//int min; // 最小距离临时变量
		let curNode = 0; // 临时结点，记录当前正计算结点
		let dist = new Array<number>(length), prev = new Array<number>(length);

		// 初始结点信息
		for (let v = 0; v < length; v++) {
			s[v] = false;
			dist[v] = graph[start][v];
			if (dist[v] > Dijkstra.MaxSize) {
				prev[v] = 0;
			} else {
				prev[v] = start;
			}
		}
		path[0] = end;
		dist[start] = 0;
		s[start] = true;
		// 主循环
		for (let i = 1; i < length; i++) {
			let min = Dijkstra.MaxSize;
			for (let w = 0; w < length; w++) {
				if (!s[w] && dist[w] && dist[w] < min) {
					curNode = w;
					min = dist[w];
				}
			}

			s[curNode] = true;

			for (let j = 0; j < length; j++) {
				let wt = graph[curNode][j] ? graph[curNode][j] : 2000;
				let wt2 = dist[j] ? dist[j] : 2000;
				if (!s[j] && min + wt < wt2) {
					dist[j] = min + graph[curNode][j];
					prev[j] = curNode;
				}
			}
		}
		// 输出路径结点
		let e = end, step = 0;
		while (e != start) {
			step++;
			path[step] = prev[e];
			e = prev[e];
		}
		for (let i = step; i > step / 2; i--) {
			let temp = path[step - i];
			path[step - i] = path[i];
			path[i] = temp;
		}
		s = null;
		return dist[end];
	}

	/** 从某一源点出发，找到到所有结点的最短路径
	 * @param graph 图数据，它是一个二维矩阵，记录每两个点之间的距离
	 * @param start 起始节点索引号
	 * @param path 二维数据，用于返回start到每个顶点之间的路径
	 * @return 数组，从start到每个点之间的距离
	 */
	public static getShortedPathAll(graph: number[][], start: number, path: number[][]): number[] {
		let length = graph.length;
		//let PathID = new Array<number>(length);// 路径（用编号表示）
		let s = new Array<boolean>(length); // 表示找到起始结点与当前结点间的最短路径
		let min = Dijkstra.MaxSize; // 最小距离临时变量
		let curNode = 0; // 临时结点，记录当前正计算结点
		let dist = new Array<number>(length), prev = new Array<number>(length);
		// 初始结点信息

		for (let v = 0; v < length; v++) {
			s[v] = false;
			dist[v] = graph[start][v];
			//if (dist[v] == null || dist[v] > Dijkstra.MaxSize) {
			if (dist[v] == undefined || dist[v] > Dijkstra.MaxSize) {
				prev[v] = 0;
			} else {
				prev[v] = start;
			}
			path[v][0] = v;
		}

		dist[start] = 0;
		s[start] = true;
		// 主循环
		for (let i = 1; i < length; i++) {
			min = Dijkstra.MaxSize;
			for (let w = 0; w < length; w++) {
				if (!s[w] && dist[w] && dist[w] < min) {
					curNode = w;
					min = dist[w];
				}
			}

			s[curNode] = true;

			for (let j = 0; j < length; j++) {
				let wt = graph[curNode][j];
				if (!wt) {
					wt = 2000;
				}
				let wt2 = dist[j];
				if (!wt2) {
					wt2 = 2000;
				}
				if (!s[j] && (min + wt < wt2)) {
					dist[j] = min + graph[curNode][j];
					prev[j] = curNode;
				}
			}
		}
		// 输出路径结点
		for (let k = 0; k < length; k++) {
			let e = k, step = 0;
			while (e != start) {
				step++;
				path[k][step] = prev[e];
				e = prev[e];
			}
			for (let i = step; i > step / 2; i--) {
				let temp = path[k][step - i];
				path[k][step - i] = path[k][i];
				path[k][i] = temp;
			}
		}
		s = null;
		return dist;

	}

}