赞
踩
Dijkstra算法解决图中某特定点到其他点的最短路径。
迪杰斯塔拉(Dijkstra)算法思想:
按路径长度递增的次序产生最短路径的算法。设集合S存放已经找到最短路径的顶点,V为所有节点的集合,S的初始状态只包含源点V0,对Vi∈V-S。
假设从源点V0到Vi的有向边为最短路径,以后每求得一条最短路V0……Vk,就把Vk加入集合S里,并将路径V0……Vk,Vi与原来的假设比较,取路径较短者为最短路径。
重复上述过程,直到集合V中全部顶点加入集合S里。算法结束。
理解:
①对于集合S和集合V-S,每次迭代都把集合V-S中与源点V0距离最小的点Vk加入集合S,
②然后重新计算集合V-S中所有点与V0的最短距离
③如果所有点都已经加入S则结束,否则继续从①开始
- /*************************************************************************
- > File Name: Dijkstra.cpp
- > Author: Shorey
- > Mail: shoreybupt@gmail.com
- > Created Time: 2015年04月24日 星期五 17时12分25秒
- ************************************************************************/
-
- #include<iostream>
- #include<stdlib.h>
- #include<stdio.h>
- #include<stack>
- #define M 100
- #define N 100
- #define INT_MAX 10000
- using namespace std;
- typedef struct node
- {
- int matrix[N][M];
- int n;
- int e;
- }MGraph;
-
- void DijkstraPath(MGraph g, int *dist, int *path, int v0)//v0表示源顶点
- {
- bool *visited = new bool[g.n];
- for(int i=0; i<g.n; i++) //初始化工作
- {
- if(g.matrix[v0][i]>0 && i!=v0)
- {
- dist[i] = g.matrix[v0][i];
- path[i] = v0;
- }
- else
- {
- dist[i] = INT_MAX; //若i不与v0直接相邻,则权值为无穷大
- path[i] = -1;
- }
- visited[i] = false;
- path[v0] = v0;
- dist[v0] = 0;
- }
- visited[v0] = true; //v0设为已经访问
-
- for(int i=1; i<g.n; i++) //循环n-1次,寻找把剩余结点加入的路径
- {
- int min = INT_MAX;
- int u;
- for(int j=0; j<g.n; j++)//寻找未被扩展的权值最小的顶点
- {
- if(visited[j]==false && dist[j]<min)
- {
- min = dist[j];
- u = j;
- }
- }
- visited[u] = true;//把上步找到的结点加入路径中
- for(int k=0; k<g.n; k++)//更新dist数组的值和路径的值
- {
- if(visited[k]==false && g.matrix[u][k]>0 && min+g.matrix[u][k]<dist[k])
- {
- dist[k] = min+g.matrix[u][k];
- path[k] = u;
- }
- }
- }
- }
-
- void showPath(int *path, int v, int v0)
- {
- stack<int> s;
- int u = v;
- while(v!=v0)
- {
- s.push(v);
- v = path[v];
- }
- s.push(v);
- while(!s.empty())
- {
- printf("%d ",s.top());
- s.pop();
- }
- }
- int main()
- {
- int n,e;
- while(scanf("%d%d",&n,&e) && e!=0)
- {
- MGraph g;
- int v0;
- int *dist = new int[n];
- int *path = new int[n];
- for(int i=0; i<N; i++)
- for(int j=0; j<M; j++)
- g.matrix[i][j] = 0;
- g.n = n;
- g.e = e;
- for(int i=0; i<e; i++)
- {
- int s,t,w;
- scanf("%d%d%d",&s,&t,&w);
- g.matrix[s][t] = w;
- }
- scanf("%d",&v0);
- DijkstraPath(g, dist, path, v0);
- for(int i=0; i<n; i++)
- {
- if(i!=v0)
- {
- showPath(path, i, v0);
- printf("%d\n",dist[i]);
- }
- }
- }
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。