Dijkstra算法

傷城~ 2022-05-09 05:36 166阅读 0赞

C++向量版本：

模块化了算法，可以直接在其他函数调用

#include<iostream>
    #include<vector>
    using namespace std;
    
    void init1(vector<vector<int>> &e, int &n)		//向量初始化
    {
    	e.resize(n+1);	//初始化的利器呀！！！
    	for (int i = 1; i <= n; i++)
    	{
    		e[i].resize(n+1);
    		for (int j = 1; j <= n; j++)
    		{
    			if (i == j)
    				e[i][j] = 0;
    			else
    				e[i][j] = INT_MAX;
    		}
    	}
    }
    void init2(vector<vector<int>> &e, vector<int> &dis, vector<int> &visit, int &n)	//初始化其他两个向量
    {
    	dis.resize(n+1);
    	visit.resize(n+1);
    	//初始化dis数组，1号顶点到其余各个顶点的初始距离 
    	for (int i = 1; i <= n; i++)
    	{
    		dis[i] = e[1][i];
    	}
    	//初始化visit数组
    	for (int i = 1; i <= n; i++)
    	{
    		visit[i] = 0;
    	}
    	visit[1] = 1;
    }
    void dijkstra(vector<vector<int>> &e, vector<int> &dis, vector<int> &visit, int &n)
    {
    	int i, j, u = 0, v, min;
    	for (i = 1; i <= n - 1; i++)
    	{
    		//找离1号顶点最近的顶点 1.未访问 2.最小 
    		min = INT_MAX;							//32位 最大值 = 65536
    		for (j = 1; j <= n; j++)				//遍历所有的节点（1-n）
    		{
    			if (visit[j] == 0 && dis[j] < min)	//1.未访问 2.最小
    			{
    				min = dis[j];					//赋值给min，且记录最小值的位置
    				u = j;	//记录位置
    			}
    		}
    		visit[u] = 1;							//将访问位置置为1，每次仅置一个位置
    
    
    		/*
    		 *		通过v遍历来更新距离的节点，来传递
    		 *		1,该点是可达的，相邻的
    		 *		2.未访问的更新最短距离
    		 */
    
    		//更新还没有访问的距离（间接距离与直接距离）
    		for (v = 1; v <= n; v++)				//遍历所有未访问的节点
    		{
    			if (e[u][v] < INT_MAX)	//可达
    			{
    				if (visit[v] == 0 && dis[v] > dis[u] + e[u][v])	  //1.未访问 2. 距离最小
    					dis[v] = dis[u] + e[u][v];
    			}
    		}
    	}
    }
    
    int main()
    {
    	int t1, t2, t3;
    	int n, m;
    	vector<vector<int >> e;//存储邻接矩阵
    	vector<int> dis;		//最短距离
    	vector<int> visit;		//访问标志
    	cin >> n >> m;
    
    	init1(e, n);
    
    	//读入边 
    	for (int i = 1; i <= m; i++)
    	{
    		cin >> t1 >> t2 >> t3;
    		e[t1][t2] = t3;
    	}
    	init2(e, dis, visit, n);
    	dijkstra(e, dis, visit, n);
    	for (int i = 1; i <= n; i++)
    	{
    		cout << dis[i] << endl;
    	}
    
    	system("pause");
    	return 0;
    }

C++数组版本：

**参考啊哈磊《啊哈！算法》**

#include<iostream>
    using namespace std;
    int e[111][111],dis[111],visit[111];
    int n,m;
    const int inf=999999;
    void init1()    //i到i的节点设置为0，其余设为不可达
    {
        for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(i==j)
    			e[i][j]=0;
    			else
    			e[i][j]=inf;
    		}
    	}
    }
    void init2()//根据输入的数值，将
    {
    	//初始化dis数组，1号顶点到其余各个顶点的初始距离 
    	for(int i=1;i<=n;i++)
    	{
    		dis[i]=e[1][i];
    	}
    	//初始化visit数组
    	for(int i=1;i<=n;i++)
    	{
    		visit[i]=0;
    	}
    	visit[1]=1; 
    }
    void dijkstra()
    {
    	int i,j,u,v,min;
    	for(i=1;i<=n-1;i++)
    	{
    		//找离1号顶点最近的顶点 
    		min=inf;
    		for(j=1;j<=n;j++)
    		{
    			if(visit[j]==0&&dis[j]<min)
    			{
    				min=dis[j];
    				u=j;
    			}
    		}
    		visit[u]=1;
    		for(v=1;v<=n;v++)
    		{
    			if(e[u][v]<inf)
    			{
    				if(visit[v]==0&&dis[v]>dis[u]+e[u][v])
    				dis[v]=dis[u]+e[u][v];
    			}
    		}
    	}
    }
    int main()
    {
    	int i,j,t1,t2,t3;
    	cin>>n>>m;
    	init1();
    	//读入边 
    	for(i=1;i<=m;i++)
    	{
    		cin>>t1>>t2>>t3;
    		e[t1][t2]=t3;
    	}
    	init2(); 
    	dijkstra();
    	for(i=1;i<=n;i++)
    	{
    		cout<<dis[i]<<endl;
    	}
    	return 0;
    }