Dijkstra最短路径算法的C ++程序？

  • Z时代
  • 2024-01-10
  • 分类：综合

Dijkstra的算法（或Dijkstra的最短路径优先算法，SPF算法）是一种用于在图形中的节点之间找到最短路径的算法，例如，该图形可表示道路网络。该算法创建了一条从起始顶点（源）到图中所有其他点的最短路径树。

Dijkstra的算法通过构建与源之间的距离最小的一组节点，从单个源节点中找到最短路径树。

该图具有以下内容-

  • 顶点或节点，在算法中以v或u表示。

  • 连接两个节点的加权边：(u,v)表示一条边，而w(u,v)表示其权重。在右图中，每个边缘的权重用灰色表示。


算法步骤

  • 设置除源顶点以外的所有顶点的距离=无穷大，将源距离设置为0。

  • 将源顶点按格式(distance,vertex)推入最小优先级队列，因为最小优先级队列中的比较将根据顶点距离进行。

  • 弹出与优先级队列距离最小的顶点（首先弹出的顶点=源）。

  • 在“当前顶点距离+边缘权重<下一个顶点距离”的情况下，更新已连接顶点到弹出顶点的距离，然后将具有新距离的顶点推入优先级队列。

  • 如果之前访问了弹出的顶点，请继续使用而不使用它。

  • 再次应用相同的算法，直到优先级队列为空。

给定一个图和图中的一个源顶点，找到从源到给定图中所有顶点的最短路径。给定图权重的G [] []矩阵，图中n个顶点（起始节点）不存在。

输入值

G[max][max]={{0,1,0,3,10},
   {1,0,5,0,0},
   {0,5,0,2,1},
   {3,0,2,0,6},
   {10,0,1,6,0}}
n=5
u=0

输出结果

Distance of node1=1
Path=1<-0
Distance of node2=5
Path=2<-3<-0
Distance of node3=3
Path=3<-0
Distance of node4=6
Path=4<-2<-3<-0

说明

  • 根据邻接矩阵adj [] []创建成本矩阵C [] []。C [i] [j]是从顶点i到顶点j的成本。如果顶点i和j之间没有边，则C [i] [j]为无穷大。

  • 数组Visited []初始化为零。

for(i=0;i<n;i++)
   visited[i]=0;

  • 如果顶点0是源顶点，则Visited [0]被标记为1。

  • 通过存储顶点编号为0的顶点的成本来创建距离矩阵。从源顶点0到0到n-1。

for(i=1;i<n;i++)
distance[i]=cost[0][i];

最初，源顶点的距离为0。即distance [0] = 0;

for(i=1;i<n;i++)
visited[i]=0;

  • 选择一个顶点w，以使distance [w]最小且visited [w]为0。将Visited [w]标记为1。

  • 重新计算剩余顶点到源的最短距离。

  • 仅，在重新计算距离时，应考虑在访问的数组[]中未标记为1的顶点。即对于每个顶点v

if(visited[v]==0)
   distance[v]=min(distance[v],
   distance[w]+cost[w][v])

示例

#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
   int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}};
   int n=5;
   int u=0;
   dijkstra(G,n,u);
   return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
   int cost[max][max],distance[max],pred[max];
   int visited[max],count,mindistance,nextnode,i,j;
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
   if(G[i][j]==0)
      cost[i][j]=INFINITY;
   else
      cost[i][j]=G[i][j];
   for(i=0;i<n;i++) {
      distance[i]=cost[startnode][i];
      pred[i]=startnode;
      visited[i]=0;
   }
   distance[startnode]=0;
   visited[startnode]=1;
   count=1;
   while(count<n-1) {
      mindistance=INFINITY;
      for(i=0;i<n;i++)
         if(distance[i]<mindistance&&!visited[i]) {
         mindistance=distance[i];
         nextnode=i;
      }
      visited[nextnode]=1;
      for(i=0;i<n;i++)
         if(!visited[i])
      if(mindistance+cost[nextnode][i]<distance[i]) {
         distance[i]=mindistance+cost[nextnode][i];
         pred[i]=nextnode;
      }
      count++;
   }
   for(i=0;i<n;i++)
   if(i!=startnode) {
      cout<<"\nDistance of node"<<i<<"="<<distance[i];
      cout<<"\nPath="<<i;
      j=i;
      do {
         j=pred[j];
         cout<<"<-"<<j;
      }while(j!=startnode);
   }
}

以上是 Dijkstra最短路径算法的C ++程序？ 的全部内容， 来源链接： utcz.com/z/338133.html

回到顶部