dijkstra输出最短路径代码实现

Dijkstra算法输出最短路径的代码实现：
1.初始化dist数组和visited数组，dist数组存储起点到各个点的最短距离，visited数组记录各个点是否被访问。
2.将起点的dist值设为0，visited值设为true。
3.对与起点相邻的点进行松弛操作，即更新其dist值（如果需要），扩展到与相邻点相邻的未访问点。
4.从未被访问的dist值最小的点开始，重复步骤3，直到找到终点或所有点都被访问。
5.如果终点被访问，则输出起点到终点的最短距离和路径，否则不存在从起点到终点的路径。

核心代码示例（使用邻接矩阵存储图）：

1.初始化：

int n; //节点数
int[][MAXN] G; //邻接矩阵表示图
int[] dist = new int[n];
boolean[] visited = new boolean[n];
for(int i=0; i<n; i++){
dist[i] = INF;
visited[i] = false;
}
dist[start] = 0;

2.松弛操作：

for(int j=0; j<n; j++){
if(G[i][j]!=INF && !visited[j] && dist[i]+G[i][j]<dist[j]){
dist[j] = dist[i]+G[i][j];
}
}

3.查找最小dist值的点：

int minDist = INF;
int u = -1;
for(int i=0; i<n; i++){
if(!visited[i] && dist[i]<minDist){
minDist = dist[i];
u = i;
}
}

完整代码：

static final int INF = Integer.MAX_VALUE;
public static void dijkstra(int start, int end) {
int n = G.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
int[] path = new int[n]; //保存路径
for(int i=0; i<n; i++){
dist[i] = INF;
visited[i] = false;
path[i] = -1;
}
dist[start] = 0;
while(!visited[end]){
int minDist = INF;
int u = -1;
for(int i=0; i<n; i++){
if(!visited[i] && dist[i]<minDist){
minDist = dist[i];
u = i;
}
}
if(u == -1) break;
visited[u] = true;
for(int j=0; j<n; j++){
if(G[u][j]!=INF && !visited[j] && dist[u]+G[u][j]<dist[j]){
dist[j] = dist[u]+G[u][j]; //松弛操作
path[j] = u; //记录路径
}
}
}
if(visited[end]){
System.out.println("起点到终点最短距离为："+dist[end]);
System.out.print("最短路径为："+end);
int p = path[end];
while(p!=-1){
System.out.print("->"+p);
p = path[p];
}
} else {
System.out.println("不存在从起点到终点的路径！");
}
}