Dijkstra(迪杰斯特拉)算法

简介

　　Dijkstra(迪杰斯特拉)是典型的单源最短路径算

法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路 径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号 方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

 

算法描述

　　(这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)

　　1． 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 　　2． 在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3 　　3． 对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2

 

复杂度分析

　　Dijkstra 算法的时间复杂度为O(n^2)

　　空间复杂度取决于存储方式，邻接矩阵为O(n^2)

算法实现

输入输出格式

　　输入格式:

　　第1行:一个数n，代表有n个节点 　　第2-n+1行:每行n个数，代表图的邻接矩阵，没有边相连为-1 　　输出格式: 　　第1行:n-1个数，分别是1号节点到2-n号节点的最短路径

输入文件dijkstra.in

700 20 50 30 00 00 0020 00 25 00 00 70 0050 25 00 40 25 50 0030 00 40 00 55 00 0000 00 25 55 00 10 0000 70 50 00 10 00 0000 00 00 00 00 00 00

程序文件dijkstra.pas

program dijkstra;varstate:array[1..100]of boolean;data:array[1..100,1..100]of longint;n,i,j,k,min,node:longint;begin	assign(input,'dijkstra.in');	assign(output,'dijkstra.out');	reset(input);	rewrite(output);	fillchar(data, sizeof(data), 0);	fillchar(state,sizeof(state),0);	readln(n);	for i:=1 to n do	for j:=1 to n do	begin		read(data[i,j]);		if data[i,j]=0 then data[i,j]:=maxint;	end;	state[1]:=true;	for k:=2 to n do	begin		min:=maxint;		{查找权值最小的点为node}		node:=1;		for i:=2 to n do		if (data[1,i]
    
     maxint then		write(data[1,i],' ')	else		write(-1,' ');	writeln(data[1,n]);	close(input);	close(output);end.
    

编译运行后会产生输出文件dijkstra.out

$ fpc dijkstra.pas Free Pascal Compiler version 3.0.4 [2017/10/03] for x86_64Copyright (c) 1993-2017 by Florian Klaempfl and othersTarget OS: Linux for x86-64Compiling dijkstra.pasLinking dijkstra/usr/bin/ld: 警告: link.res 含有输出节；您忘记了 -T？47 lines compiled, 0.1 sec$ ./dijkstra $ cat dijkstra.out -1 20 45 30 70 80 32767

c++实现代码：

#include
    
     #include
     
      using namespace std;const int MaxNum=1000000; //边权最大值int n; //节点数目int dist[501]; //到节点1的最短路径值bool state[501]; //节点被搜索过状态指示int data[501][501]; //邻接矩阵//查找权值最小的节点int findmin(){	int minnode=0, min=MaxNum;	for(int i=1; i<=n; i++)	  if ((dist[i]
      
       > n;	for(int p=1; p<=n; p++)	  for(int q=1; q<=n; q++)	  {		  in >> data[p][q];		  if (data[p][q]==0) data[p][q]=MaxNum;	  }	//初始化	for(int i=1; i<=n; i++)	  dist[i]=data[1][i];	state[1]=true;	int done=1;	while (done
       
        dist[node]+data[node][i]) && (!state[i]))				dist[i]=dist[node]+data[node][i];		}		else break;	}	for(int p=1; p<=n; p++)	{		if (dist[p]==MaxNum)		  out<<-1;		else		  out<
       
      
     
    

dijkstra.in文件与前面一样的。

C++实现另一版本Dijkstra.cpp：

/* * * 问题 F: 求最短距离及其花费 * 题目描述 * 由n个点和m条无向边构成的无向连通图，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费， * 如果最短距离有多条路线，则输出花费最少的。 * 请用Dijkstra算法或Floyd算法等求解！ * 输入 * 输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t; 起点s，终点t。 * (2<=n<=2000, n-1<=m<=(n*(n-1))/2, 1<=d<=10000, 1<=p<=10000, s != t) * 输出 * 输出：一行有两个数， 最短距离及其花费。 * 样例输入 * 3 2 * 1 2 5 6 * 2 3 4 5 * 1 3 * 样例输出 * 9 11 * * * * */#include
    
     using namespace std;#define MAX 9999999int map[2005][2005],pay[2005][2005];int used[2005],dist[2005],pas[2005];int p,q,n;int i,j;void dijkstra(){    for(i=1;i<=n;i++)    {        dist[i]=map[p][i];        pas[i]=pay[p][i];        used[i]=0;    }    dist[p]=0;    used[p]=1;    int num=1;    while(num
     
      dist[pos]+map[pos][i])                {                    dist[i]=dist[pos]+map[pos][i];                    pas[i]=pas[pos]+pay[pos][i];                }                else if(dist[i]==dist[pos]+map[pos][i]&&pas[i]>pas[pos]+pay[pos][i])                    pas[i]=pas[pos]+pay[pos][i];            }        }    }    cout<
      
       <<" "<
       
        <
        
         >n>>m&&n&&m)    {        for(i=0;i<=j;i++)            for(j=0;j<=n;j++)            {                map[i][j]=MAX;                pay[i][j]=MAX;            }           for(i=0;i
         
          >a>>b>>c>>d; if(map[a][b]>c) { map[a][b]=map[b][a]=c; pay[a][b]=pay[b][a]=d; } } cin>>p>>q; dijkstra(); } return 0;}
         
        
       
      
     
    

编译运行：

$ g++ -o Dijkstra Dijkstra.cpp $ ./Dijkstra 3 21 2 5 62 3 4 51 39 11

参考：