题目描述
求一个顶点到其他顶点的最短距离。
总体思路
假设有集合S和集合T,一开始S中只有源点,T中有除源点之外的所有顶点。
每次循环将集合T中距离源点最近的顶点X加入集合S中,得出源点到该顶点的最短距离。再继续一次循环,如果源点到顶点X的距离 + 顶点X到集合T中的顶点的距离 < 集合T中的顶点到源点的距离,那么更新集合T中的顶点到源点的距离为源点到顶点X的距离 + 顶点X到集合T中的顶点的距离。
循环到集合T中没有顶点就结束。
邻接矩阵
public class Dijkstra {
// matrix是有向图数组,如果顶点间没有相连,那么值设为10000
public static int[] dijkstra(int[][] matrix, int source) {
int len = matrix.length;
int[] shortest = new int[len];
boolean[] vis = new boolean[len];
shortest[source] = 0;
vis[source] = true;
for (int i = 1; i < len; i++) {
int min = Integer.MAX_VALUE;
int index = -1;
for (int j = 0; j < len; j++) {
if (!vis[j] && matrix[source][j] < min) {
min = matrix[source][j];
index = j;
}
}
shortest[index] = min;
vis[index] = true;
for (int j = 0; j < len; j++) {
if (!vis[j] && matrix[source][index] + matrix[index][j] < matrix[source][j]) {
matrix[source][j] = matrix[source][index] + matrix[index][j];
}
}
}
return shortest;
}
public static void main(String[] args) {
int MaxValue = 10000;
int[][] matrix = {
{MaxValue,MaxValue,10,MaxValue,30,100},
{MaxValue,MaxValue,5,MaxValue,MaxValue,MaxValue},
{MaxValue,MaxValue,MaxValue,50,MaxValue,MaxValue},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,10},
{MaxValue,MaxValue,MaxValue,20,MaxValue,60},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}
};
int source = 0;
int[] path = dijkstra(matrix, source);
for (int i = 0; i < path.length; i++) {
if (path[i] == 0) continue;
if (path[i] == 10000) {
System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + "不可达");
}
else {
System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + path[i]);
}
}
}
}
邻接链表
public class DijkstraListNode {
static class Node {
// 终点
int to;
// 权重
int w;
// 下一个结点
Node next;
public int getTo() {
return to;
}
public void setTo(int to) {
this.to = to;
}
public int getW() {
return w;
}
public void setW(int w) {
this.w = w;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(int to, int w, Node node) {
this.to = to;
this.w = w;
this.next = node;
}
@Override
public String toString() {
return this.to + "," + this.w;
}
}
// 邻接矩阵转邻接链表
public static Node[] createListNode(int[][] matrix) {
int len = matrix.length;
Node[] res = new Node[len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (matrix[i][j] > 0 && matrix[i][j] < 10000) {
Node node = new Node(j, matrix[i][j], res[i]);
res[i] = node;
}
}
}
return res;
}
public static int[] dijkstra(Node[] path, int source) {
int len = path.length;
int[] shortest = new int[len];
boolean[] vis = new boolean[len];
shortest[0] = 0;
vis[0] = true;
Node temp = path[source];
while (temp != null) {
shortest[temp.getTo()] = temp.getW();
temp = temp.next;
}
for (int i = 1; i < len; i++) {
if (shortest[i] == 0) {
shortest[i] = 10000;
}
}
for (int i = 1; i < len; i++) {
int min = Integer.MAX_VALUE;
int index = -1;
for (int j = 1; j < len; j++) {
if (!vis[j] && shortest[j] < min) {
min = shortest[j];
index = j;
}
}
shortest[index] = min;
vis[index] = true;
for (int j = 1; j < len; j++) {
if (!vis[j]) {
Node cur = path[index];
while (cur != null) {
if (cur.getTo() == j) {
break;
}
cur = cur.next;
}
if (cur != null) {
shortest[j] = Math.min(shortest[j], min + cur.getW());
}
}
}
}
return shortest;
}
public static void main(String[] args) {
int MaxValue = 10000;
int[][] matrix = {
{MaxValue,MaxValue,10,MaxValue,30,100},
{MaxValue,MaxValue,5,MaxValue,MaxValue,MaxValue},
{MaxValue,MaxValue,MaxValue,50,MaxValue,MaxValue},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,10},
{MaxValue,MaxValue,MaxValue,20,MaxValue,60},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}
};
Node[] res = createListNode(matrix);
int source = 0;
int[] path = dijkstra(res, source);
for (int i = 0; i < path.length; i++) {
if (path[i] == 0) continue;
if (path[i] == 10000) {
System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + "不可达");
}
else {
System.out.println("顶点" + source + "->顶点" + i + "的最短距离:" + path[i]);
}
}
}
}
结果打印
顶点0->顶点1的最短距离:不可达
顶点0->顶点2的最短距离:10
顶点0->顶点3的最短距离:50
顶点0->顶点4的最短距离:30
顶点0->顶点5的最短距离:60
版权声明:本文为weixin_52272771原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。