国家住房城乡建设厅网站,wordpress投票模板,营销网络平台,门户网站有哪些类型迪杰斯特拉算法(Diikstra) 是由荷兰计算机科学家狄克斯特拉于1959 年提出的#xff0c;因此又叫狄克斯特拉算法。
核心思想#xff0c;搜索到某一个顶点后#xff0c;更新与其相邻顶点的权重。顶点权重的数据含义表示从起始点到此点的最短路径长度#xff08;也就是经过的…迪杰斯特拉算法(Diikstra) 是由荷兰计算机科学家狄克斯特拉于1959 年提出的因此又叫狄克斯特拉算法。
核心思想搜索到某一个顶点后更新与其相邻顶点的权重。顶点权重的数据含义表示从起始点到此点的最短路径长度也就是经过的所有边的权重之和。DJ 算法搜索时每次选择的下一个顶点是所有权重值最小的顶点其思想是保证每一次选择的顶点和当前顶点权重都是最短的。所以DJ是基于贪心思想。
矩阵存储
常规时间复杂度O(n)可以使用堆优化优先队列时间复杂度降低到O(logN)。缺点是对于稀疏图而言空间浪费严重。
#include bits/stdc.h
using namespace std;//矩阵存储图
int graph[100][100];
//顶点、边数
int v,e;
//优先队列使用数组
int pri[100];
//存储起点到其它顶点之间的最短距离
int dis[100];
//设置无穷大常量
int const INF INT_MAX;/*
*初始化函数
*/
void init()
{//初始化图中顶点之间的关系for(int i1; iv; i){for(int j1; jv; j){if( ij ){//自己和自己的关系权重为 0graph[i][j]0;}else{//任意两点间的距离为无穷大graph[i][j]INF;}}}//交互式确定图中顶点之间的关系int f,t,w;for( int i1; ie; i ){cinftw;graph[f][t]w;}//初始设编号为 1 的顶点为起始点,根据顶点的关系初始化起点到其它顶点之间的距离for(int i1; iv; i){dis[i]graph[1][i];}//初始化优先队列也称为候选队列for(int i1; iv; i ){if(i1){//起始顶点默认为已经候选pri[i]1;continue;}//其它顶点都可候选pri[i]0;}}/*
*
*Dijkstra算法
*/
void dijkstra()
{for(int i1; iv; i){//从候选队列中选择一个顶点要求到起始顶点的距离为最近的int u-1;int miINF;for( int j1; jv; j ){if(pri[j]0 dis[j]mi){midis[j];uj;}}if(u!-1)//找到后设置为已经候选pri[u]1;else //找不到就结束break;//查找与此候选顶点相邻的顶点且更新邻接点与起点之间的距离//相当于在此顶点基础上向后延长for( int j1; jv; j ){if( graph[u][j]!INF ){//找到相邻顶点if(dis[j]dis[u]graph[u][j] ){//更新dis[j]dis[u]graph[u][j];}}}}}/*
*
*显示最后的结果
*/
void show()
{for(int i1; iv; i){coutdis[i]\t;}
}int main()
{cinve;init();dijkstra();show();return 0;
}
//测试用例
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
//输出
0 1 8 4 13 17邻接表
整个时间复杂度可以优化到O(MN)logN。在最坏的情况下M(边数)就是N顶点数这样的话(MM)logN要比N还要大。但是大多数情况下并不会有那么多边因此(MM)logN要比N小很多。
#include bits/stdc.husing namespace std;
/*
* 顶点类型
*/
struct Ver
{//顶点编号int vid0;//第一个邻接点int head0;//起点到此顶点的距离顶点权重,初始为 0 或者无穷大int dis0;//重载函数bool operator( const Ver ver ) const{return this-disver.dis;}void desc(){coutvid disendl;}
};/*
* 边
*/
struct Edge
{//邻接点int to;//下一个int next0;//权重int weight;
};class Graph
{
private:const int INFINT_MAX;//存储所有顶点Ver vers[100];//存储所有边Edge edges[100];//顶点数边数int v,e;//起点到其它顶点之间的最短距离int dis[100];//优先队列priority_queueVer proQue;public:Graph( int v,int e ){this-vv;this-ee;init();}void init(){for(int i1;iv;i){//重置顶点信息vers[i].vidi;vers[i].disINF;vers[i].head0;}int f,t,w;for(int i1; ie; i){cinftw;//设置边的信息edges[i].tot;edges[i].weightw;//头部插入edges[i].nextvers[f].head;vers[f].headi;}for(int i1; iv; i){dis[i]vers[i].dis;}}void dijkstra(int start){//初始化优先队列,起点到起点的距离为 0vers[start].dis0;dis[start]0;proQue.push(vers[start]);while( !proQue.empty() ){//出队列Ver verproQue.top();ver.desc();proQue.pop();//找到邻接顶点 i 是边集合索引号for( int iver.head; i!0; iedges[i].next){int vedges[i].to;//更新距离if( vers[ v ].dis ver.dis edges[i].weight ){vers[ v ].dis ver.disedges[i].weight;dis[ v ] vers[ v ].dis;//入队列proQue.push( vers[v] );}}}}void show(){for(int i1; iv; i){coutdis[i]\t;}}};int main()
{int v,e;cinve;Graph graph(v,e);int s;cins;graph.dijkstra(s);graph.show();return 0;
}
