来自当知百科
跳转到: 导航搜索

目录

算法简介

  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号节点的最短路径

C++

  #include<fstream>

  #include<cstring>

  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]<min) && (!state[i]))

  {

  min=dist[i];

  minnode=i;

  }

  return minnode;

  }

  int main()

  {

  ifstream in("dijkstra.in");

  ofstream out("dijkstra.out");

  memset(state, 0, sizeof(state));

  in >> 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<n)

  {

  int node=findmin();

  if (node!=0)

  {

  done++; //找到的点的数目加1

  state[node]=true; //标记已经找到了从节点1到节点node的最短路径

  for(int i=1; i<=n; i++)//更新还没有找到的点的路径值

  if ((dist[i]>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<<dist[p];

  if (p==n)

  out<<endl;

  else

  out<<" ";

  }

  in.close();

  out.close();

  return 0;

  }

Pascal

  program dijkstra;

  var

  state: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]<min)and(state[i]=false) then

  begin

  min:=data[1,i];

  node:=i;

  end;

  {更新其他各点的权值}

  state[node]:=true;

  for j:=1 to n do

  if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false)then

  data[1,j]:=data[1,node]+data[node,j];

  end;

  for i:=1 to n-1 do

  if data[1,i]<>maxint then

  write(data[1,i],' ')

  else

  write(-1,' ');

  writeln(data[1,n]);

  close(input);

  close(output);

  end.

测试样例

  Sample Input

  7

  00 20 50 30 00 00 00

  20 00 25 00 00 70 00

  50 25 00 40 25 50 00

  30 00 40 00 55 00 00

  00 00 25 55 00 10 00

  00 70 50 00 10 00 00

  00 00 00 00 00 00 00

  Sample Output

  -1 20 45 30 70 80 -1

个人工具
名字空间

变换
查看
操作
导航
工具箱