Dijkstra算法解决单源最短路径问题实例

1、实例题

用Dijkstra算法解决单源最短路径问题，并给出算法的时间复杂性分析。用你写的程序求出下图节点1到任何一个节点的最短路径，包括最短路径值及其最短路径。

2、Java实现

https://blog.csdn.net/carson0408/article/details/78634650

main函数：

Dijkstra类：

package com.dynamicProgramming;import java.util.HashMap;import java.util.LinkedList;import java.util.Queue;public class Dijkstra{private Queue visited;private int[] distance;public Dijkstra(int len) {    // TODO Auto-generated constructor stub    visited=new LinkedList();    distance=new int[len];}private int getIndex(Queue q,int[] dis){    int k=-1;    int min_num=Integer.MAX_VALUE;    for(int i=0;idis.length;i++)    { if(!q.contains(i)) {if(dis[i]min_num){ min_num=dis[i]; k=i;} }    }    return k;}public void dijkstra(int[][] weight,Object[] str,int v){    HashMap path;    path=new HashMap();    for(int i=0;istr.length;i++) path.put(i, "");    //初始化路径长度数组distance    for(int i=0;istr.length;i++)    { path.put(i, path.get(i)+""+str[v]); if(i==v)distance[i]=0; else if(weight[v][i]!=-1) {distance[i]=weight[v][i];path.put(i, path.get来源：暮白-像鱼忘了海
                                                        
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！