单源最短路径

《单源最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单源最短路径xie_dream给定带权有向图G=(V,E)和源点u,求从点u到其他各顶点的最短距离Dijkstra算法基本思想是：设置一个集合Ｓ存放已经找到最短路径的顶点，Ｓ的初始状态只包含源点u,设置另一个集合Ｔ，Ｔ＝Ｖ-Ｓ，存储原图中不在Ｓ集中的点，即Ｓ的补集。假设从源点u到vi的有向边为最短路径，以后每求得一条最短路径v,…,vk就将vk加入集合Ｓ中，并将路径v,…vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合Ｖ中全部顶点加入到集合Ｓ中STuviSTuvivkST

2、uvivkuv2v3v4v133512992S集合红线右侧全为Ｔ集合1)先假设v1,v2,v3,v4与u相连的边就是最短路径dist[v1]=3,dist[v2]=2;dist[3]=9;dist[4]=10v2v3v4v1331012992S集合uu2)找一个离u最近的点加入S集合(这里是不是有点象前一讲中的MST的Prim算法),即为v2v2v3v4v1331012992S集合u2)找一个离u最近的点加入S集合(这里是不是有点象前一讲中的MST的Prim算法),即为v2v2v3v4v13310129

3、92S集合u再用v2去检查从v2可到达的点的原先的所有假设发现dist[v4]>dist[v2]+g[v2][v4],更新dist[v4]v2v3v4v1331012992S集合u3)按上一步同样的方法找到v1加入到S集合中v2v3v4v1331012992S集合u3)按上一步同样的方法找到v1加入到S集合中v2v3v4v1331012992S集合u４)按上一步同样的方法找到v4加入到S集合中,这时dist[v3]=9

4、t[v4]=4了！v2v3v4v1331012992S集合u５)４加入Ｓ集合中，同样发现dist[v3]>dist[v4]+g[v4][v3],更新！v2v3v4v1331012992S集合u算法实现过程1,初始化dist[]和color[]2,while(s集合中的元素个数小于n)在dist[]中求最小值，并同样记录下标k用dist[k]去修改k一步直接可达的点的dist[]将顶点k放入Ｓ集合中，染为紫色详细代码/*Author:PrimeMusic_FanCreatedon2010年4月29日,下午

5、1:46*/#include#include#definearr110#defineblue0#definepurple1#definemax_int214748364intn;//thenumberofvertexsintm;//thenumberofedgesintg[arr][arr];//g[i][j]indicatesthedistancebetweeniandjintpath[arr];//path[i]recordtheshorestpathfroms

6、ourceutoiintdist[arr];//dist[i]indicatestheshortestdistancefromutoiintst;//thesourcevertexintcolor[arr];//colorthevertexvoidDijkstra(intst){for(inti=1;i<=n;++i){color[i]=blue;dist[i]=g[st][i];//先假设源点u到其他点的直接相连边的长度就为最短距离path[i]=st;//假设都是从u直接通过一条有向边到达}dist

7、[st]=0;color[st]=purple;intnumS=1;//S集合中元素的个数,已经加入了源点，所以为１while(numS++dist[i]){minDis=dist[i];k=i;}}//print

8、f("k=%d",k);if(k==-1)//说明找不到与源点相连的点，算法结束break;color[k]=purple;//找到点k，加入Ｓ集合中，并染为紫色//下一步，用dist[k]去检查原先的所有不在Ｓ集合，即Ｔ集合中所有点的假设for(inti=1;i<=n;++i){if(color[i]==purple)continue;if(dist[i]>dist[k]+g[k][i]){//通过点k可以使源点到i点的距离变小，更新