- // exam1.cpp : 定义控制台应用程序的入口点。
- //
- #include "stdafx.h"
- #include <iostream>
- #include <stack>
- using namespace std;
- #define MAXVEX 20
- #define INT_MAX 10000
- typedef struct ArcNode
- {
- int adj;
- void* info;
- }ArcNode;
- typedef ArcNode AdjMat[MAXVEX][MAXVEX];
- typedef struct
- {
- int vexnum;
- int arcnum;
- AdjMat am;
- }Graph;
- void InitGraph(Graph& G)
- {
- cout<<"Please enter the number of vertex:"<<endl;
- cin>>G.vexnum;
- cout<<"Please enter the Arc of the graph:"<<endl;
- cout<<"head tail weight"<<endl;
- for(int i=0;i<G.vexnum;i++)
- {
- for(int j=0;j<G.vexnum;j++)
- {
- if(i==j)
- {
- G.am[i][j].adj=0;
- }
- else
- {
- G.am[i][j].adj=INT_MAX;
- }
- }
- }
- int vex1,vex2,w;
- while(cin>>vex1>>vex2>>w)
- {
- G.am[vex1][vex2].adj=w;
- }
- }
- void ShortestPath_DIJ(Graph G,bool** path)
- {
- int *D;
- D=(int*)malloc(G.vexnum*sizeof(int));
- bool *final;
- final=(bool*)malloc(G.vexnum*sizeof(bool));
- memset(final,G.vexnum*sizeof(bool));
- for(int i=0;i<G.vexnum;i++)
- {
- D[i]=INT_MAX;
- if(G.am[0][i].adj<INT_MAX)
- {
- D[i]=G.am[0][i].adj;
- }
- path[i][i]=true; //terminal point
- path[i][0]=true; //starting point
- }
- final[0]=true;
- for(int i=1;i<G.vexnum;i++)
- {
- int min=INT_MAX;
- int min_indx=-1;
- for(int j=0;j<G.vexnum;j++)
- {
- if(final[j]==false)
- {
- if(D[j]<min)
- {
- min=D[j];
- min_indx=j;
- }
- }
- }
- final[min_indx]=true;
- if(min_indx!=-1)
- {
- for(int j=1;j<G.vexnum;j++)
- {
- if(final[j]==false)
- {
- if(D[j]>D[min_indx]+G.am[min_indx][j].adj)
- {
- D[j]=D[min_indx]+G.am[min_indx][j].adj;
- for(int k=0;k<G.vexnum;k++)
- {
- path[j][k]=path[min_indx][k];
- }
- path[j][j]=true;
- }
- }
- }
- }
- }
- cout<<"The shortest path from v0 to "<<endl;
- for(int j=0;j<G.vexnum;j++)
- {
- cout<<"v"<<j<<":"<<D[j]<<endl;
- for(int i=0;i<G.vexnum;i++)
- {
- cout<<path[j][i]<<" ";
- }
- cout<<endl;
- }
- }
- int main(void)
- {
- Graph G;
- InitGraph(G);
- bool **path;
- path=(bool**)malloc(G.vexnum*sizeof(bool*));
- for(int i=0;i<G.vexnum;i++)
- {
- path[i]=(bool*)malloc(G.vexnum*sizeof(bool));
- memset(path[i],false,G.vexnum*sizeof(bool));
- }
- ShortestPath_DIJ(G,path);
- system("pause");
- return 0;
- }