最短路径—DIGSKRA算法

AC代码：

//重新编写最短路径算法
#include <iostream>
#include <cstring>
#define max_vex 1001  //最多结点个数---不要加分号
#define inf 0x3f3f3f3f   //十进制为1061109567，int 取值范围--2147483648 ~2147483647
using namespace std;
int value[max_vex][max_vex];  //存储边的权值
int visited[max_vex];   //标记该结点是否加入最短路径
int dist[max_vex];     //标记该结点至源点地最近距离
int vex, arc,start;   //读取结点与边的数据
void DIG(int start)
{
	//初始化visited数组
	memset(visited, 0, sizeof(visited));    //刚开始谁都没访问过
	for (int i = 0; i < vex; ++i) {
		dist[i] = value[start][i];     //源点start到各个结点的最小距离
	}
	//将源点放到最短路径结点集合中
	visited[start] = 1;
	//更新最短距离数组
	dist[start] = 0;
	int num = 1;   //每一轮循环将一个数值放入到最短路径结点集合中
	while (num < vex)
	{
		//找出剩余节点中路径最短的结点
		int minn = inf;
		int t_i = 0;  //记录最短路径结点的下标
		for (int i = 0; i < vex; ++i) {
			//前提是不在最短路径结点集合中
			if (visited[i] == 0 && minn > dist[i]) {
				minn = dist[i];   //就是那个最短路径的数值
				t_i = i;
			}
		}
		//将刚刚找到的节点加入到集合中
		visited[t_i] = 1;   //已经标记了
		num++;    //最短路径结点结合中结点数加1
		//将这个结点加入到路径中后，更新所有节点到源点地最短路径
		for (int i = 0; i < vex; ++i) {
			//对非集合中的节点的最短路径进行更新
			if (visited[i] == 0 && (dist[i] > dist[t_i] + value[t_i][i]))
			{
				//原来源点距离i的距离大于刚刚取得结点的最短路径加上该点至i的路径距离
				dist[i] = dist[t_i] + value[t_i][i];
			}
		}
	}
	//输出重点end的最短路径   ---判断一下end值是否有效
	for(int i=0;i<vex;++i){
		if(i!=start){
			if(dist[i]!=inf){
				cout<<dist[i]<<" ";
			}
			else
			{
				cout<<"-1"<<" ";
			}
		}
	}
	cout<<endl;
}
int main() {
	//输入数据，不必创建一个图
	cin >> vex >> start;
	for(int i=0;i<vex;i++){
		for(int j=0;j<vex;j++){
			cin>>value[i][j];
			if(value[i][j]==0){     
			    //将0转为inf，便于后续计算，不然给dist数组赋值时，会是0（代表路径距离为0） 
			    value[i][j]=inf;
			}
		}
	}
	//至此邻接矩阵构造完毕
	if (start >= 0 && start < vex) {
		DIG(start);
	}
	return 0;
}