Dijkstra算法 单源最短路径算法.doc

Dijkstra算法单源最短路径算法
来源:百度百科
算法简介
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
算法描述(这里描述的是从节点1开始到各点的dijkstra算法,其中Wa-b表示a-b的边的权值,d(i)即为最短路径值)
={2,3,.n},数组d(1)=0,d(i)=W1-i(1,i之间存在边)or+无穷大()
,令d(j)=min{d(i),i属于S},令S=S-{j},若S为空集则算法结束,否则转3 ,如果存在边j-i,那么置d(i)=min{d(i),d(j)+Wj-i},转2
复杂度分析Dijkstra算法的时间复杂度为O(n^2)
空间复杂度取决于存储方式,邻接矩阵为O(n^2)
算法实现
////Dijkstra算法
//Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。
//输入格式:
//第1行:一个数n,代表有n个节点
//第2-(n+1)行:每行n个数,代表图的邻接矩阵,没有边相连为-1
//输出格式:
//第1行:n-1个数,分别是1号节点到(2-n)号节点的最短路径
//输入:,内容如下:
//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
//输出:,如下:
//-1 20 45 30 70 80-1
//PS:百度百科给出答案为//40 20 45 30 70 80-1
#include fstream
#include cstring using namespace std;
const int MaxNum=;//边权最大值
int n;//节点数目
int dist[501];//到节点1的最短路径值
bool state[501];//节点被搜索过状态指示
int data[501][501];//邻接矩阵
//查找权值最小的节点
int findmin(void)
{
int minnode=0,min=MaxNum;
for(int i=1;i=n;i++)
if((dist min)&&(!state))
{
min=dist;
minnode=i;
}
return minnode;
}
int main(void)
{
ifstream in("d