图之最短距离的Dijkstra算法

本文主要是介绍图之最短距离的Dijkstra算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

该算法和最小生成树的Prim算法十分相似

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXEDGE 100
#define MAXVEX 100
#define INFINITY 65535
struct MGraph
{char V[10];int Edge[10][10];int Vexnum;int Edgenum;
};
void CreateGraph(MGraph *G)  //初始化邻接矩阵
{  printf("请输入顶点数和边数：");  scanf("%d%d",&(G->Vexnum),&(G->Edgenum));  char c;  c=getchar();  int i,j;  for(i=0;i<G->Vexnum;i++)  for(j=0;j<G->Vexnum;j++)  G->Edge[i][j]=INFINITY;  printf("请输入顶点信息（char）型\n");  for(i=0;i<G->Vexnum;i++)  scanf("%c",&(G->V[i]));  c=getchar(); int w;  for(int k=0;k<G->Edgenum;k++)  {  printf("请输入(vi,vj)的下标i,j和权值w:");  scanf("%d%d%d",&i,&j,&w);  c=getchar();  G->Edge[i][j]=w;  G->Edge[j][i]=w;  } }  
int min(int a,int b)
{return a<b?a:b;
}int d[MAXVEX];void Dijkstra(int s,MGraph G)
{bool used[MAXVEX];fill(used,used+G.Vexnum,false);fill(d,d+G.Vexnum,INFINITY);d[s]=0;while(true){int v=-1;for(int i=0;i<G.Vexnum;i++){if(!used[i]&&(v==-1||d[i]<d[v]))v=i;}if(-1==v)break;used[v]=true;for(int k=0;k<G.Vexnum;k++){d[k]=min(d[k],d[v]+G.Edge[v][k]);}}}
void main()
{MGraph G;CreateGraph(&G);int s=0;Dijkstra(s,G);for(int i=0;i<G.Vexnum;i++)printf("原点%c到%c点的最小距离是:%d\n",G.V[s],G.V[i],d[i]);}

这篇关于图之最短距离的Dijkstra算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---