加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Dijkstra算法(迪杰斯特拉算法)

(2013-08-05 22:49:29)
标签:

dijkstra算法

c

it

分类: 数据结构

Dijkstra算法(迪杰斯特拉算法)

Dijkstra算法用于求单源点点最短路径问题,问题描述如下:给定带权有向图G=(V,E)和源点 V,求从v到G中其余的顶点的最短路径。

迪杰斯特拉提出来一个按路径长度递增的次序产生最短路径的算法,其基本思想是:设置一个集合S存放已经找到的最短路径的顶点,S的初始状态只包含源点v,对vi V-S,假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,……,vk,就将vk加入集合S中,并将路径v,……,vk,vi与原来的假设相比较,取路径长度较小者为当前最短路径,重复上述过程,直到集合V中全部顶点加入到集合S中。所需总的时间复杂度是O(n2)

伪代码如下:

1.  初始化数组dist,close和vnum;

2.  while(S中元素的个数

2.1在dist[n]中求最小值,其编号为k;

2.2输出dist[k]和close;

2.3修改数组dist和close;

2.4将顶点k添加到数组s中;

例子如下:

Dijkstra算法(迪杰斯特拉算法)

具体用C++来实现

dijkstra.txt中的内容

1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60

 

dijkstra.cpp程序如下:

#include
#include
#define MAX 1000     //假设1000是其权值最大和达不到的一个数


int dist[10];  //用来存储每个点到点1的距离,假设最大的结点数为10
int vist[10]={0};   //用来存储点访问情况
int close[10][10];  //用来存储邻接矩阵
int n, //节点的数目
int m,x,y;
int mindistance()   //找寻当前状态下到达目标节点路径最短的点
{
    int minnode = 0,min = MAX;
    for(int i = 1;i <= n;i++)
        if(min > dist[i] && !vist[i])
        {
            min = dist[i];
            minnode = i;
        }
    return minnode;
}

int main()
{
 using namespace std;
    int i,j,vnum;
 cout<<"请输入结点数:"<<endl;
    cin >> n;
 cout<<"请输入边数:"<<endl;
 cin>>m;


 //初始化close[i][j]
 
 for(i = 1;i <= n;i++)
        for(j = 1;j <= n;j++)
        {
   close[i][j] = MAX;
        }

   
 fstream fin;
 fin.open("dijkstra.txt");
 for (i=0;i<=m;i++)
 {
  fin>>x;
  fin>>y;
  fin>>close[x][y];
   
 }


 
    for(i = 1;i <= n;i++) 
  dist[i] = close[1][i];   //考虑其他结点到结点1的最短路径
    vist[1] = 1;  //节点1已归入集合S中
    vnum = 1;       //归入集合S中节点的数量

    while(vnum < n)
    {
        int node = mindistance();
        if(node != 0)
        {
            vnum ++;
            vist[node] = true;


            for(i = 1;i <=  n;i++)
                if(dist[i] > dist[node] + close[node][i] && !vist[i])
                    dist[i] = dist[node] +close[node][i];
        }
        else    break;
    }


    for(i = 1;i <= n;i++)
    {
        if(dist[i] == MAX)
            cout<<-1<<" ";//1到1点的距离记为-1
        else    cout<<dist[i]<<" ";
    }
    return 0;
}

运行结果如下:

 Dijkstra算法(迪杰斯特拉算法)

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有