算法导论|算法导论-单源最短路径-Dijkstra算法的实现
public class Dijkstra {
static int M=10000;
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] weight1 = {
{0,3,2000,7,M},
{3,0,4,2,M},
{M,4,0,5,4},
{7,2,5,0,6},
{M,M,4,6,0}
};
//有向图的矩阵表示，数值表示权重
int[][] weight2 = {
{0,10,M,30,100},
{M,0,50,M,M},
{M,M,0,M,10},
{M,M,20,0,60},
{M,M,M,M,0}
};
int start=0;
//起点s
int[] shortPath = Dijsktra(weight2,start);
for(int i = 0;
i < shortPath.length;
i++)
System.out.println("从"+start+"出发到"+i+"的最短距离为："+shortPath[i]);
}public static int[] Dijsktra(int[][] weight,int start){
//接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
//返回一个int[] 数组，表示从start到它的最短路径长度
int n = weight.length;
//顶点个数
int[] shortPath = new int[n];
//存放从start到其他各点的最短路径
String[] path=new String[n];
//存放从start到其他各点的最短路径的字符串表示
for(int i=0;
i< n;
i++)
path[i]=new String(start+"-->"+i);
int[] visited = new int[n];
//标记当前该顶点的最短路径是否已经求出,1表示已求出//初始化，第一个顶点求出
shortPath[start] = 0;
visited[start] = 1;
for(int count = 1;
count <= n - 1;
count++)//要加入n-1个顶点
{
int k = -1;
//选出一个距离初始顶点start最近的未标记顶点
int dmin = Integer.MAX_VALUE;
for(int i = 0;
i < n;
i++)
{
if(visited[i] == 0 && weight[start][i] < dmin)
{
dmin = weight[start][i];
k = i;
}}//将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
shortPath[k] = dmin;
visited[k] = 1;
//以k为中间点，修正从start到未访问各点的距离。每有一个新结点被访问，便要修正，根据是最短路径的最优子结构性质
for(int i = 0;
i < n;
i++)
{
if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]){
weight[start][i] = weight[start][k] + weight[k][i];
path[i]=path[k]+"-->"+i;
}}}
for(int i=0;
i< n;
i++)
System.out.println("从"+start+"出发到"+i+"的最短路径为："+path[i]);
System.out.println("=====================================");
return shortPath;
}
}【算法导论|算法导论-单源最短路径-Dijkstra算法的实现】
根据迪杰斯特拉算法的原理，简单用C语言实现：
#include using namespace std;
#define M 10000void Dijsktra(int weight[][5], int start);
int dis[5];
int used[5]={0,0,0,0,0};
int main()
{
int weight2[][5]={
{0,10,M,30,100},
{M,0,50,M,M},
{M,M,0,M,10},
{M,M,20,0,60},
{M,M,M,M,0}
};
int start=0;
Dijsktra(weight2, start);
for(int i=0;
i<5;
i++)
cout< 参考2用C语言重新实现了Dijkstra算法，原作者的C语言写的不错，值得我学习。我根据其代码做了轻微的修改，使之更加简练。这里把源代码贴出来，便于以后复习。
#include
#include
#define max 9999
void Dijkstra(int ,int,int *,int *,int **);
void Search(int,int,int*);
int main()
{
int i,j,num,v,last;
//num表示点的个数，v表示起始点；
FILE *p;
//2.txt中第一个数据表示点的个数，第二个数据表示起始点；
//其他数据为图中点之间的可达关系，-1表示不可达
p=fopen("a.txt","r");
if(!p)
{
printf("cannot open file 2.txt");
exit(0);
}
fscanf(p,"%d",&num);
//获得点的个数
printf("请输入起始点：");
scanf("%d",&v);
int *d=(int*)malloc(sizeof(int)*num);
//prev[]用于记录最短路径中每个点的前一个点
int *prev=(int *)malloc(sizeof(int)*num);
//a[][]用于记录各个点之间的路径，-1表示不可直达，具体数据参见a.txt；
int **a=(int**)malloc(sizeof(int*)*num);
for(i=0;
i参考1：http://www.java3z.com/cwbwebhome/article/article1/1341.html?id=4645
参考2：http://www.cnblogs.com/lpshou/archive/2012/04/20/2459102.html
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 简谈迪克斯特拉算法