锐客网

  1. 首页 > it技术 > >

dijkstra 解决单元最短路（无负权）

算法

算法思路：dijkstra算法是把结点分为两个集合，一个是已经求出最短路的集合S，另一个就是其他结点的集合U，一开始S只有源结点V0，dijkstra算法就是不断的冲U集合中找出离中转点最近的点，然后把它加入到S集合中，加入后更新U集合的数据。
模拟一遍：一开始只有S只有v0源点，然后在U集合中找到了离v0最近的结点k，把k加入到S中，并把U中的结点数据更新。更新规则如下：if（dist[u]+map[u][j] 具体代码如下：
【dijkstra 解决单元最短路（无负权）】

#include using namespace std; #define maxn 100 #define inf 9999999 int ma[maxn][maxn]; int dist[maxn]; int n,m,v,e; int ai,bi,num; int s[maxn]; void dijkstra(int v) { for(int i=1; i<=n; i++)//初始化dist和s数组 { dist[i]=ma[v][i]; s[i]=0; } dist[v]=0; //一开始S中只有v s[v]=1; for(int i=2; i<=n; i++)//循环n-1次，知道把所有结点都加到S中 { int u; int mi=inf; for(int j=1; j<=n; j++)//在U中找最小dist { if(!s[j]&&mi>dist[j]) { mi=dist[j]; u=j; } } s[u]=1; for(int j=1; j<=n; j++)//如果dist[j]+ma[u][j]dist[u]+ma[u][j]) { dist[j]=dist[u]+ma[u][j]; } } } } } int main() { memset(ma,inf,sizeof(ma)); memset(s,0,sizeof(s)); scanf("%d %d",&n,&m); //n为节点数，m为边数 scanf("%d %d",&v,&e); //源点v和终点e for(int i=1; i<=m; i++) { scanf("%d %d %d",&ai,&bi,&num); ma[ai][bi]=num; // ma[bi][ai]=num; //无向图的操作 } memset(dist,inf,sizeof(dist)); dijkstra(v); printf("%d\n",dist[e]); }



    推荐阅读


    上一篇：Ui|AutomationElement.AutomationElementInfomation.NativeWindowHandle

    下一篇：MEMS加速度计中的核心简介