用java怎么用迪杰斯特拉算有向图有权值的最短路径

　Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

创新互联网站建设公司，提供网站建设、网站设计，网页设计，建网站，PHP网站建设等专业做网站服务;可快速的进行网站开发网页制作和功能扩展；专业做搜索引擎喜爱的网站，是专业的做网站团队，希望更多企业前来合作!

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式

用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：

1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点

2.初始阶段，将初始节点放入close，其他所有节点放入open

3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：

Node对象用于封装节点信息，包括名字和子节点

[java] view plain copy

public class Node {

private String name;

private MapNode,Integer child=new HashMapNode,Integer();

public Node(String name){

this.name=name;

}

public String getName() {

return name;

}

public void setName(String name) {

this.name = name;

}

public MapNode, Integer getChild() {

return child;

}

public void setChild(MapNode, Integer child) {

this.child = child;

}

}

MapBuilder用于初始化数据源，返回图的起始节点

[java] view plain copy

public class MapBuilder {

public Node build(SetNode open, SetNode close){

Node nodeA=new Node("A");

Node nodeB=new Node("B");

Node nodeC=new Node("C");

Node nodeD=new Node("D");

Node nodeE=new Node("E");

Node nodeF=new Node("F");

Node nodeG=new Node("G");

Node nodeH=new Node("H");

nodeA.getChild().put(nodeB, 1);

nodeA.getChild().put(nodeC, 1);

nodeA.getChild().put(nodeD, 4);

nodeA.getChild().put(nodeG, 5);

nodeA.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeA, 1);

nodeB.getChild().put(nodeF, 2);

nodeB.getChild().put(nodeH, 4);

nodeC.getChild().put(nodeA, 1);

nodeC.getChild().put(nodeG, 3);

nodeD.getChild().put(nodeA, 4);

nodeD.getChild().put(nodeE, 1);

nodeE.getChild().put(nodeD, 1);

nodeE.getChild().put(nodeF, 1);

nodeF.getChild().put(nodeE, 1);

nodeF.getChild().put(nodeB, 2);

nodeF.getChild().put(nodeA, 2);

nodeG.getChild().put(nodeC, 3);

nodeG.getChild().put(nodeA, 5);

nodeG.getChild().put(nodeH, 1);

nodeH.getChild().put(nodeB, 4);

nodeH.getChild().put(nodeG, 1);

open.add(nodeB);

open.add(nodeC);

open.add(nodeD);

open.add(nodeE);

open.add(nodeF);

open.add(nodeG);

open.add(nodeH);

close.add(nodeA);

return nodeA;

}

}

图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径

[java] view plain copy

public class Dijkstra {

SetNode open=new HashSetNode();

SetNode close=new HashSetNode();

MapString,Integer path=new HashMapString,Integer();//封装路径距离

MapString,String pathInfo=new HashMapString,String();//封装路径信息

public Node init(){

//初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUE

path.put("B", 1);

pathInfo.put("B", "A-B");

path.put("C", 1);

pathInfo.put("C", "A-C");

path.put("D", 4);

pathInfo.put("D", "A-D");

path.put("E", Integer.MAX_VALUE);

pathInfo.put("E", "A");

path.put("F", 2);

pathInfo.put("F", "A-F");

path.put("G", 5);

pathInfo.put("G", "A-G");

path.put("H", Integer.MAX_VALUE);

pathInfo.put("H", "A");

//将初始节点放入close,其他节点放入open

Node start=new MapBuilder().build(open,close);

return start;

}

public void computePath(Node start){

Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close

if(nearest==null){

return;

}

close.add(nearest);

open.remove(nearest);

MapNode,Integer childs=nearest.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){//如果子节点在open中

Integer newCompute=path.get(nearest.getName())+childs.get(child);

if(path.get(child.getName())newCompute){//之前设置的距离大于新计算出来的距离

path.put(child.getName(), newCompute);

pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"-"+child.getName());

}

}

}

computePath(start);//重复执行自己,确保所有子节点被遍历

computePath(nearest);//向外一层层递归,直至所有顶点被遍历

}

public void printPathInfo(){

SetMap.EntryString, String pathInfos=pathInfo.entrySet();

for(Map.EntryString, String pathInfo:pathInfos){

System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());

}

}

/**

* 获取与node最近的子节点

*/

private Node getShortestPath(Node node){

Node res=null;

int minDis=Integer.MAX_VALUE;

MapNode,Integer childs=node.getChild();

for(Node child:childs.keySet()){

if(open.contains(child)){

int distance=childs.get(child);

if(distanceminDis){

minDis=distance;

res=child;

}

}

}

return res;

}

}

Main用于测试Dijkstra对象

[java] view plain copy

public class Main {

public static void main(String[] args) {

Dijkstra test=new Dijkstra();

Node start=test.init();

test.computePath(start);

test.printPathInfo();

}

}

求PROMETHEE-II算法代码

Dijkstra算法

1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法描述

1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则u,v正常有权值，若u不是v的出边邻接点，则u,v权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

执行动画过程如下图

3.算法代码实现：

复制代码

const int MAXINT = 32767;

const int MAXNUM = 10;

int dist[MAXNUM];

int prev[MAXNUM];

int A[MAXUNM][MAXNUM];

void Dijkstra(int v0)

{

bool S[MAXNUM]; // 判断是否已存入该点到S集合中

int n=MAXNUM;

for(int i=1; i=n; ++i)

{

dist[i] = A[v0][i];

S[i] = false; // 初始都未用过该点

if(dist[i] == MAXINT)

prev[i] = -1;

else

prev[i] = v0;

}

　 dist[v0] = 0;

　 S[v0] = true;

for(int i=2; i=n; i++)

{

int mindist = MAXINT;

int u = v0; // 找出当前未使用的点j的dist[j]最小值

for(int j=1; j=n; ++j)

if((!S[j]) dist[j]mindist)

{

u = j; // u保存当前邻接点中距离最小的点的号码

　 　 mindist = dist[j];

}

S[u] = true;

for(int j=1; j=n; j++)

if((!S[j]) A[u][j]MAXINT)

{

　 　if(dist[u] + A[u][j] dist[j]) //在通过新加入的u点路径找到离v0点更短的路径

　 　{

dist[j] = dist[u] + A[u][j]; //更新dist

prev[j] = u; //记录前驱顶点

}

　 　}

}

}

遗传算法求最短路径

#includestdio.h

#includeiostream

#includestring.h

#includemalloc.h

#includestdlib.h

#includestring

using namespace std;

#define OVERFLOW -2

#define OK 1

#define ERROR 0

#define INFINITY 200//最大值

#define MAX_VERTEX_NUM 20//最大顶点个数

typedef char VertexType;//定义为char类型

//以下是全局变量,用于保存弗洛伊德算法的路径和长度

int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径长度

int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径标记

//以下是全局变量,用于保存迪杰斯特拉算法的路径和长度

int Distance[MAX_VERTEX_NUM];

VertexType former[MAX_VERTEX_NUM];//终点的前一个顶点

bool final[MAX_VERTEX_NUM];//记录顶点是否在V-S中

typedef struct ArcCell

{

int adj; //顶点关系类型

int weight; //该弧相关信息的指针,在此记录为权值

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct

{

VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

AdjMatrix arcs; //邻接矩阵

int vexnum; //顶点数

int arcnum; //弧数

}MGraph;

void InitialMGraph(MGraph G)//初始化

{

G.arcnum=G.vexnum=0; //初始化边数跟顶点数都为零

for(int i=0;iMAX_VERTEX_NUM;i++)

for(int j=0;jMAX_VERTEX_NUM;j++)

{

if(i==j)

G.arcs[i][j].weight=0;

else

G.arcs[i][j].weight=INFINITY; //初始化为200,以200认为是无穷大

}

}

void InsertVex(MGraph G,VertexType v)//插入顶点

{

if(G.vexnum=MAX_VERTEX_NUM)

G.vexs[G.vexnum++]=v;

}

void InsertArc(MGraph G,VertexType v1,VertexType v2)//插入边

{

int m,n;

G.arcnum++;

for(int k=0;kG.vexnum;k++)

{

if(G.vexs[k]==v1)

m=k;

if(G.vexs[k]==v2)

n=k;

}

//插入

ArcCell A;

cout"请输入权值:";

cinA.weight;

G.arcs[m][n].weight=A.weight;

}

//迪杰斯特拉最短路径,假设始点就存储在数组中的第一个

void ShortestPath_DIJ(MGraph G,int v0)

{

//初始化距离

for(int v=0;vG.vexnum;++v)

{

final[v]=false;

Distance[v]=G.arcs[v0][v].weight;

if(Distance[v]INFINITYDistance[v]!=0)

{

former[v]=G.vexs[v0];

}

else

former[v]='#';

}

final[v0]=true;

former[v0]=G.vexs[v0];

for(int i=1;iG.vexnum;++i)//剩余的G.vexnum-1个顶点

{

int w;

int min=INFINITY;

int v=-1;

for(w=0;wG.vexnum;++w)

{

if(!final[w]Distance[w]min)

{

v=w;

min=Distance[w];

}

}

if(v!=-1)

{

final[v]=true;//将离顶点V0最近的顶点v加入S集合中

for(w=0;wG.vexnum;++w)//更新当前的最短路径及距离

{

if(!final[w](min+G.arcs[v][w].weightDistance[w])G.arcs[v][w].weightINFINITY)

{

Distance[w]=min+G.arcs[v][w].weight;

former[w]=G.vexs[v];

}

}

}

}

}

//输出迪杰斯特拉中的最短路径

void output_ShortestPath_DIJ(MGraph G,int v0)

{

int i;

for(i=1;iG.vexnum;i++)

{

coutG.vexs[v0]"-"G.vexs[i]":";

if(Distance[i]!=INFINITY)

{

cout"最短路径长度为:"Distance[i]" 最短路径的前一个顶点为:"former[i];

coutendl;

}

else

cout"此两顶点之间不存在路径"endl;

}

}

//弗洛伊德最短路径

void shortestPath_FLOYD(MGraph G)

{

for(int v=0;vG.vexnum;++v)

{

for(int w=0;wG.vexnum;++w)

{

D[v][w]=G.arcs[v][w].weight;

for (int k=0;k G.vexnum;k++)

P[v][w][k]=-1;

if(D[v][w]INFINITY) //从v到w有直接路径

P[v][w][v]=w;

}

}

for(int k=0;kG.vexnum;++k)

{

for(int v=0;vG.vexnum;v++)

for(int w=0;wG.vexnum;++w)

if(D[v][w]D[v][k]+D[k][w])

{

D[v][w]=D[v][k]+D[k][w];

for(int i=0;iG.vexnum;i++)

{

if(P[v][k][i]!=-1)//原来存了顶点

P[v][w][i]=P[v][k][i];

else

P[v][w][i]=P[k][w][i];

}

}

}

}

//输出弗洛伊德中的最短路径

void output_shortestPath_FLOYD(MGraph G)

{

for(int i=0;iG.vexnum;++i)

{

for(int j=0;jG.vexnum;++j)

{

if(i!=j)//自己不能到达自己

{

coutG.vexs[i]"-"G.vexs[j]":";

if(D[i][j]==INFINITY)

{

cout"此两顶点之间不存在路径"endl;

}

else

{

cout"最短路径长度为:"" "D[i][j]" ";

cout"最短路径为:";

coutG.vexs[i];

for(int k=i;k!=-1;k=P[i][j][k])

{

if(k!=i)

coutG.vexs[k];

}

coutendl;

}

}

}

}

}

int main()

{

int num1;//顶点个数

int num2;//弧个数

cout"请输入顶点个数:";

cinnum1;

cout"请输入弧个数:";

cinnum2;

VertexType v;

MGraph G;

InitialMGraph(G);

cout"请输入顶点的信息:"endl;

for(int i=0;inum1;++i)

{

cinv;;

InsertVex(G,v);

}

VertexType v1,v2;

for(int j=0;jnum2;++j)

{

cout"请输入两个结点数据来表示的边:";

cinv1v2;

InsertArc(G,v1,v2);

}

ShortestPath_DIJ(G,0);

cout"迪杰斯特拉中的最短路径如下:"endl;

output_ShortestPath_DIJ(G,0);

coutendlendl;

shortestPath_FLOYD(G);

cout"弗洛伊德中的最短路径如下:"endl;

output_shortestPath_FLOYD(G);

return 0;

}

寻求大神帮忙写Java代码，要用Dijkstra’s algorithm（迪杰斯特拉算法）

package minRoad.no;

import java.util.Arrays;

//这个程序用来求得一个图的最短路径矩阵

public class ShortestDistance_V4 {

private static final int inf = Integer.MAX_VALUE;// 表示两个点之间无法直接连通

public static int[][] dijkstra(int[][] graph) {

int min, v, u = 0, n = graph.length;

int[] path = new int[n];

int[] dist = new int[n];

boolean[] s = new boolean[n];

Arrays.fill(s, false);

Arrays.fill(dist, inf);

for (int i = 0; i n; i++) {

dist[i] = graph[u][i];

if (i != u dist[i] inf)

path[i] = u;

else

path[i] = -1;

}

s[u] = true;

while (true) {

min = inf;

v = -1;

// 找到最小的dist

for (int i = 0; i n; i++) {

if (!s[i]) {

if (dist[i] min) {

min = dist[i];

v = i;

}

}

}

if (v == -1) break;// 找不到更短的路径了

// 更新最短路径

s[v] = true;

for (int i = 0; i n; i++) {

if (!s[i] graph[v][i] != inf dist[v] + graph[v][i] dist[i]) {

dist[i] = dist[v] + graph[v][i];

path[i] = v;

}

}

}

// 输出路径

int[] shortest = new int[n];

for (int i = 1; i n; i++) {

Arrays.fill(shortest, 0);

int k = 0;

shortest[k] = i;

while (path[shortest[k]] != 0) {

k++;

shortest[k] = path[shortest[k - 1]];

}

k++;

shortest[k] = 0;

}

int[] tmp = new int[shortest.length];

for (int i = 0; i tmp.length; i++) {

tmp[i] = shortest[tmp.length - i - 1];

}

return new int[][] { dist, tmp };

}

/**

* pre

* v0

* 1, v1

* 4, 2, v2

* inf, 7, -1, v3

* inf, 5, 1, 3, v4

* inf, inf, inf, 2, 6, v5

* /pre

*

* *

*

* pre

* A--------30-------D

* |\ ∧|

* | \ / |

* | \ / |

* | 10 10 |

* | \ / 20

* | \ / |

* | \ / |

* | ∨ / ∨

* 20 B E

* | / ∧

* | / /

* | / /

* | 5 /

* | / 30

* | / /

* | / /

* ∨∠ /

* C

* /pre

*

* @param args

*/

public static void main(String[] args) {

int[][] W1 = {

{ 0, 10, 20, 30, inf },

{ 10, 0, 5, 10, inf },

{ 20, 5, 0, inf, 30 },

{ 30, 10, inf, 0, 20 },

{ inf, inf, 30, 20, 0 },

};

//

//

// int[][] W = {

// { 0, 1, 4, inf, inf, inf },

// { 1, 0, 2, 7, 5, inf },

// { 4, 2, 0, inf, 1, inf },

// { inf, 7, inf, 0, 3, 2 },

// { inf, 5, 1, 3, 0, 6 },

// { inf, inf, inf, 2, 6, 0 }};

int[][] distAndShort = dijkstra(W1);

System.out.println(Arrays.toString(distAndShort[0]));

System.out.println(Arrays.toString(distAndShort[1]));

// distance: { 0, 1, 3, 7, 4, 9};

}

}

当前文章：迪杰斯特拉java代码 迪杰斯特拉算法伪代码
当前链接：http://ybzwz.com/article/docoooj.html