Dijkstra算法邻接矩阵C++及多种变换

int n, e[maxv][maxv] = {{0,4,inf,2,inf}, {4,0,4,1,inf}, {inf,4,0,1,3}, {2,1,1,0,7}, {inf,inf,3,7,0}}; //邻接矩阵 int dis[maxv], pre[maxv]; //pre用来标注当前节点的前一个节点 bool visit[maxv] = {false}; void Dijkstra(int s){ fill(dis, dis+maxv, inf); //给所有的距离初始化为inf dis[s] = 0; //对于节点自身为0 for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v]!=inf && dis[u]+e[u][v] < dis[v]){ dis[v] = dis[u]+e[u][v]; pre[v] = u; } } } }

int w[maxv], weight[maxv], num[maxv]; //起点到当前点的总价值，weight是静态当个点的价值，num是最短路径的个数 void Dijkstra2(int s){ //路径最短，点权权值最大，并且输出个数和路径 fill(dis, dis+maxv, inf); //给所有的距离初始化为inf fill(w, w+maxv, 0); fill(num, num+maxv, 0); dis[s] = 0; //对于节点自身为0 num[s] = 1; w[s] = weight[s]; for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v] != inf){ if(dis[u] + e[u][v] < dis[v]){ dis[v] = dis[u] + e[u][v]; //更新最短路径 num[v] = num[u]; //显然v最短路径要经过u，而u到v是固定的，因此num[v] = num[u] w[v] = w[u] + weight[v]; //更新路径的价值，路径上经过所有价值点的总和 pre[v] = u; }else if(dis[u] + e[u][v] == dis[v]){ //当有多个最短路径时 num[v] = num[u] + num[v]; //两个相加 if(w[u] + weight[v] > w[v]){ //如果价值更大则覆盖掉原先的 w[v] = w[u] + weight[v]; pre[v] = u; } } } } } }

#include<iostream> #include<cstdio> #define maxv 5 #define inf 0x7fffffff using namespace std; //邻接表 int n, e[maxv][maxv] = {{0,4,inf,2,inf}, {4,0,4,1,inf}, {inf,4,0,1,3}, {2,1,1,0,7}, {inf,inf,3,7,0}}; //邻接矩阵 int dis[maxv], pre[maxv]; //pre用来标注当前节点的前一个节点 bool visit[maxv] = {false}; void Dijkstra(int s){ fill(dis, dis+maxv, inf); //给所有的距离初始化为inf dis[s] = 0; //对于节点自身为0 for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v]!=inf && dis[u]+e[u][v] < dis[v]){ dis[v] = dis[u]+e[u][v]; pre[v] = u; } } } } int w[maxv], weight[maxv], num[maxv]; //起点到当前点的总价值，weight是静态当个点的价值，num是最短路径的个数 void Dijkstra2(int s){ //路径最短，点权权值最大，并且输出个数和路径 fill(dis, dis+maxv, inf); //给所有的距离初始化为inf fill(w, w+maxv, 0); fill(num, num+maxv, 0); dis[s] = 0; //对于节点自身为0 num[s] = 1; w[s] = weight[s]; for(int i=0;i<maxv;i++)pre[i] = i; //初始状态设每个点的前驱为自身 for(int i=0;i<maxv;i++){ //算法核心 int u = -1, minn = inf;//u代表节点，minn为最小值 for(int j=0;j<maxv;j++){ //此循环用来找到当前节点最近未访问的点 if(visit[j]==false && dis[j] < minn){ u = j; minn = dis[j]; } } if(u == -1)return; //没有对应的路径 visit[u] = true; //当前节点找到，对应于算法中加入到已访问集合 for(int v=0;v<maxv;v++){ //更新路径，如果u到其他未被选取点的距离+起点到u的距离小于起点到其他未被选取点的距离，则更新当前点的前驱为u if(visit[v] == false && e[u][v] != inf){ if(dis[u] + e[u][v] < dis[v]){ dis[v] = dis[u] + e[u][v]; //更新最短路径 num[v] = num[u]; //显然v最短路径要经过u，而u到v是固定的，因此num[v] = num[u] w[v] = w[u] + weight[v]; //更新路径的价值，路径上经过所有价值点的总和 pre[v] = u; }else if(dis[u] + e[u][v] == dis[v]){ //当有多个最短路径时 num[v] = num[u] + num[v]; //两个相加 if(w[u] + weight[v] > w[v]){ //如果价值更大则覆盖掉原先的 w[v] = w[u] + weight[v]; pre[v] = u; } } } } } } void printPath(int v){ if(v == 0){ printf("%d", v); return; } printPath(pre[v]); printf("%d ", v); } int main(){ Dijkstra(0); cout<<"distance"<<endl; for(int i=0;i<maxv;i++){ cout<<dis[i]<<endl; } cout<<endl<<"pre"<<endl; for(int i=0;i<maxv;i++){ cout<<pre[i]<<endl; } return 0; }