# 数据结构-图的创建和Dijkstra最短路径算法

## Graph Creation and Dijkstra Algorithm

Posted by xuepro on November 10, 2017

## —图的创建和Dijkstra最短路径算法–C语言版本–

#include <stdio.h>

#include <malloc.h>

#define OK 0

#define ERROR 1

typedef char VType;

typedef double WeightType;

typedef struct edgenode{
int v1,v2;
WeightType weight;
struct edgenode *next;
}EdgeNode;

typedef struct{
VType data;
EdgeNode *first;
}VNode;

typedef struct{
VNode *vertices;
int capacity,vnum;
int kind;
}Graph;

EdgeNode * newEdgeNode(){
EdgeNode* p = (EdgeNode*) malloc(sizeof(EdgeNode));
if(!p) return 0;
p->next = 0;
return p;
}

int initGraph(Graph *G,int cap){
G->vertices = (VNode *) malloc(cap*sizeof(VNode));
G->capacity = cap;
if(!G->vertices) return ERROR;
G->vnum = 0;  G->kind = 0;
return OK;
}

int insertVertex(Graph* G,VType e){
if(G->vnum==G->capacity){
VNode *p = (VNode *) realloc(G->vertices,2*G->capacity*sizeof(VNode));
if(!p) return ERROR;
//free(G->vertices);

G->vertices = p;
G->capacity = 2*G->capacity;
}
G->vertices[G->vnum].data = e;
G->vertices[G->vnum].first = 0;
G->vnum++;
return OK;
}

int insertEdge(Graph* G,int v1,int v2,WeightType weight){
EdgeNode* p  = newEdgeNode();
if(!p) return ERROR;
p->v1 = v1; p->v2 = v2; p->weight = weight;
p->next =  G->vertices[v1].first;
G->vertices[v1].first  = p;
return OK;
}

int getVertex(Graph G,int v,VType *e){
if(v<0||v>=G.vnum) return ERROR;
*e = G.vertices[v].data;
return OK;
}

EdgeNode* getFirstEdge(Graph G,int v){
if(v<0||v>=G.vnum) return 0;
return  G.vertices[v].first;
}

int *flag = 0;

void DFS(Graph G,int v){
EdgeNode *p;
printf("%c\t",G.vertices[v].data);
flag[v] = 1;
for(p = G.vertices[v].first; p; p = p ->next){
int w = p->v2;
if( flag[w]!=1)
DFS(G,w);
}
}

void DFS_Graph(Graph G){
if(flag) { free(flag); flag = 0;}
flag = (int *)malloc(G.vnum*sizeof(int));
for(int v = 0 ; v<G.vnum;v++)
flag[v]= 0;
for(int v = 0 ; v<G.vnum;v++)
if(flag[v]==0)
DFS(G,v);
}

void Dijkstra_shortest_Path(Graph G,int s,WeightType D[],int P[]);
void PrintPath(int s,WeightType D[],int P[],int vn);

int main(){
VType vdata;
int v1,v2,vn;
WeightType weight;
Graph G;
initGraph(&G,100);

printf("请 输入顶点信息:\n");
while(scanf("%c",&vdata)){
if(vdata=='\n') break;
insertVertex(&G,vdata);
}

fflush(stdin);

printf("请 输入边的信息: v1 v2 weight\n");
while(scanf("%d %d %lf",&v1,&v2,&weight)==3){
insertEdge(&G,v1,v2,weight);
}

vn = G.vnum;
for(int i = 0 ; i<vn;i++){
getVertex(G,i,&vdata);
printf("%c\t:",vdata);
EdgeNode *p = getFirstEdge(G,i);
while(p){
printf("%d %d %lf\t",p->v1,p->v2,p->weight);
p = p->next;
}
printf("\n");
}

DFS_Graph(G);

int s = 0;
WeightType *D = (WeightType *) malloc(G.vnum*sizeof(WeightType));
int *P = (int*) malloc(G.vnum*sizeof(int));
Dijkstra_shortest_Path(G,s,D,P);
PrintPath(s,D,P,G.vnum);
}

/*
----Dijkstra_shortest_Path-----

P(v) = v0;
若存在弧<V0,V>，D(v) = arcs(V0,V)
否则 D(v) = ∞

在不在S中的顶点中查找D(w)最小的顶点w
把w加入S，即w已知最短路径
更新w的所有邻接点v的D(v)
if( D(w)+c(w,v) < D(v) ){
D(v) = D(w)+arcs(w,v); P(v) = w; }
}

*/

#define INFINITY 100000000
int minVertex(WeightType D[],int S[],int vn){
int i;
for(i = 0 ; i<vn;i++){
if(S[i]==0) break;
}
if(i>=vn) return -1;

for(int j = i+1; j<vn;j++)
if(S[j]==0&& D[j]<D[i]) i  = j;

if(D[i]==INFINITY) return -2;
return i;
}

void Dijkstra_shortest_Path(Graph G,int s,WeightType D[],int P[]){
int * S = (int *)malloc(G.vnum*sizeof(int));
if(!S) return ;
for(int i = 0 ; i<G.vnum;i++){
S[i] = 0; D[i] = INFINITY;
}

S[s] = 1;
EdgeNode *p = getFirstEdge(G,s);
while(p){
D[p->v2] =  p->weight;
P[p->v2] = s;
p = p ->next;
}

while(1){
int w = minVertex(D,S,G.vnum);
if(w<0) break;
S[w] = 1;
EdgeNode *p = getFirstEdge(G,w);
while(p){
int v = p->v2;
if( D[w]+p->weight < D[v]){
D[v] = D[w]+p->weight;
P[v] = w;
}
p = p ->next;
}
}

}

void PrintPath(int s,WeightType D[],int P[],int vn){
for(int v = 0 ; v<vn;v++){
if(D[v]==INFINITY) continue;
printf("%d的逆向路径:%d",v,v);
int u = P[v]; printf("%d\t",u);
while(u!=s){
u = P[u];
printf("%d\t",u);
}
printf("\n");
}
}


## —图的创建和Dijkstra最短路径算法–C++(引用)版本–

1． 头文件 graph.h

// Graph.h: interface for the Graph class.
67C823E__INCLUDED_)
#define
NCLUDED_

#include <cassert>

#include <vector>

using namespace std;

#define NULL 0

typedef int weightType;

typedef char Type; //数据元素类型

class EdgeNode { // A singly-linked list node
public:
weightType weight; // Edge weight
int v1; // Vertex edge comes from
int v2; // Vertex edge goes to
EdgeNode* next; // Pointer to next edge in list
EdgeNode(int vt1, int vt2, weightType w, EdgeNode* nxt =NULL)
{ v1 = vt1; v2 = vt2; weight = w; next = nxt; } // Constructor
EdgeNode(EdgeNode* nxt =NULL) { next = nxt; } // Constructor
};

typedef EdgeNode* Edge;

struct VertexNode{
Type data;
Edge first;
VertexNode(Type d,Edge e):data(d),first(e){}
};

typedef VertexNode Vertex;

class Graph { // Graph class: Adjacency list
private:
vector<Vertex> list; //The vertex list
int numEdge; // Number of edges
vector<bool> Mark; // The mark array
public:
Graph(); // Constructor
~Graph(); // Destructor
int n(); // Number of vertices for graph
int e(); // Number of edges for graph
Edge first(int); // Get the first edge for a vertex
bool isEdge(Edge); // TRUE if this is an edge
Edge next(Edge); // Get next edge for a vertex
int v1(Edge); // Return vertex edge comes from
int v2(Edge); // Return vertex edge goes to
weightType weight(int, int); // Return weight of edge
weightType weight(Edge); // Return weight of edge
bool getMark(int); // Return a Mark value
void setMark(int, bool); // Set a Mark value
void setVertex(int i,Type vertexData){
assert(i>=0&&i<list.size()) ; list[i].data =vertexData; }
Type getVertex(int i){
assert(i>=0&&i<list.size()) ; return list[i].data; }
void InsertVertex ( const Type & vertexData );
void InsertEdge ( const int v1, const int v2, weightType weight );
void RemoveVertex ( const int v );
void RemoveEdge ( const int v1, const int v2 );
};

void Dijkstra_shortest_Path(Graph& G, int s,weightType D[],int P[]);

#endif
C823E__INCLUDED_)



2． cpp 文件 graph.cpp

// Graph.cpp: implementation of the Graph class.
#include "Graph.h"

#define INFINITY 1000000

Graph::Graph() { // Constructor
numEdge = 0;
}

Graph::~Graph() { // Destructor: return allocated space
// Remove all of the edges
for (int v=0; v<list.size(); v++) { // For each vertex...
Edge p = list[v].first;
while (p != NULL) { // return its edges
Edge temp = p;
p = p->next;
delete temp;
}
}
}

int Graph::n() { return list.size(); } // Number of vertices

int Graph::e() { return numEdge; } // Number of edges

Edge Graph::first(int v) // Get the first edge for a vertex
{ return list[v].first; }

bool Graph::isEdge(Edge w) // TRUE if this is an edge
{ return w != NULL; }

Edge Graph::next(Edge w) { // Get next edge for a vertex
if (w == NULL) return NULL;
else return w->next;
}

int Graph::v1(Edge w) { return w->v1; } // Vertex edge comes from

int Graph::v2(Edge w) { return w->v2; } // Vertex edge goes to

weightType Graph::weight(int i, int j) { // Return weight of edge
for (Edge curr = list[i].first; curr != NULL; curr = curr->next)
if (curr->v2 == j) return curr->weight;
return INFINITY;
}

weightType Graph::weight(Edge w) // Return weight of edge
{
if (w == NULL) return INFINITY;
else return w->weight;
}

bool Graph::getMark(int v) { return Mark[v]; }

void Graph::setMark(int v, bool val) { Mark[v] = val; }

//----------插入或删除数据-----------------------------
void Graph::InsertVertex ( const Type & vertexData ){
list.push_back( VertexNode(vertexData,NULL) );
Mark.push_back(false);
}

void Graph::InsertEdge ( const int v1, const int v2, weightType weight ){
Edge edge= new EdgeNode(v1,v2,weight);
edge->next = list[v1].first;
list[v1].first = edge;
numEdge++;
}

void Graph::RemoveVertex ( const int v ){
}

void Graph::RemoveEdge ( const int v1, const int v2 ){
}


3． 测试程序 main.cpp

#include <iostream>

#include <stack>

#include "Graph.h"

void main(){
Graph G;
Type vdata;
cout<<"请依次输入顶点数据，用'ctrl+Z' 'ctrl+Z'结束输入\n";
while(cin>>vdata){
G.InsertVertex(vdata);
}

cin.clear(); //置为正常状态

int v1 ,v2;
weightType weight;

cout<<"请输入边信息(格式为 v1 v2 weight):";
cin>>v1>>v2>>weight;

while(v1>=0&&v2>=0){
G.InsertEdge(v1,v2,weight);
cout<<"请输入边信息(格式为 v1 v2 weight):";
cin>>v1>>v2>>weight;
}

int i;
cout<<"图中顶点数据为:";
for( i = 0 ;i <G.n(); i++)
cout<<G.getVertex(i)<<" ";
cout<<endl;

cout<<"图中边数据为:";
for( i = 0 ;i <G.n(); i++){
Edge edge = G.first(i);
while(edge){
cout<<"("<<edge->v1<<" "<<edge->v2<<
" "<<edge->weight<<") ";
edge = G.next(edge);
}
}
cout<<endl;
}


1．Dijkstra 算法（Dijkstra_shortest_Path.cpp）：

#include "Graph.h"

#define INFINITY 1000000

const bool VISITED = true;

const bool UNVISITED = false;

// minVertex：在距离数组 D 中找最小的未加入 S 中的最短距离
int minVertex(Graph& G, int* D);

void Dijkstra_shortest_Path(Graph& G, int s,weightType D[],int P[])
{
// Compute shortest path distances
//初始时，所有顶点都未加入到已经最短路径的顶点集合 S

int i;
for(i = 0 ;i< G.n(); i++)
G.setMark(s, UNVISITED);

//将 s 作为起点，初始化距离数组和路径数组
for ( i=0; i<G.n(); i++){ // Initialize
D[i] = INFINITY; P[i] = s;
}

D[s] = 0; G.setMark(s, VISITED); //add s to S

for (Edge e = G.first(s); G.isEdge(e); e = G.next(e))
D[G.v2(e)] = G.weight(e);

//在未加入 S 中的顶点中选择最短路径的那个顶点，
//加入 S,并更新距离和路径数组
for (i=0; i<G.n()-1; i++) { // 最多进行 n-1 次
//在不在 S 中的顶点中查找 D(v)最小的顶点 v
int v = minVertex(G, D);
if (D[v] == INFINITY) return; // 没有可以到达的顶点了
G.setMark(v, VISITED);

//更新 v 的所有邻接点 v2 的 D(v2)和 P(v2)
for (Edge e = G.first(v); G.isEdge(e); e = G.next(e))
if (D[G.v2(e)] > (D[v] + G.weight(e))){
D[G.v2(e)] = D[v] + G.weight(e);
P[G.v2(e)] = v; //
}
}

for(i = 0 ;i< G.n(); i++)
G.setMark(s, UNVISITED);
}

int minVertex(Graph& G, int* D) { // Find min cost vertex
int v; // Initialize v to any unvisited vertex;
for (int i=0; i<G.n(); i++)
if (G.getMark(i) == UNVISITED) { v = i; break; }

for (i++; i<G.n(); i++) // Now find smallest D value
if ((G.getMark(i) == UNVISITED) && (D[i] < D[v]))
v = i;
return v;
}



2．修改后的测试程序：

#include <iostream>

#include <stack>

#include "Graph.h"

void main(){
Graph G;
Type vdata;

cout<<"请依次输入顶点数据，用'ctrl+Z' 'ctrl+Z'结束输入\n";
while(cin>>vdata)
G.InsertVertex(vdata);

cin.clear(); //置为正常状态
int v1 ,v2;
weightType weight;
cout<<"请输入边信息(格式为 v1 v2 weight):";
cin>>v1>>v2>>weight;

while(v1>=0&&v2>=0){
G.InsertEdge(v1,v2,weight);
cout<<"请输入边信息(格式为 v1 v2 weight):";
cin>>v1>>v2>>weight;
}

int i;
cout<<"图中顶点数据为:";
for( i = 0 ;i <G.n(); i++)
cout<<G.getVertex(i)<<" ";
cout<<endl;

cout<<"图中边数据为:";
for( i = 0 ;i <G.n(); i++){
Edge edge = G.first(i);
while(edge){
cout<<"("<<edge->v1<<" "<<edge->v2<<"
"<<edge->weight<<") ";
edge = G.next(edge);
}
}
cout<<endl;

//Dijkstra_shortest_Path 算法
weightType *D = new weightType[G.n()];
int *P = new int[G.n()];
int s;

cout<<"请输入起点的下标:"; cin>>s;
Type sdata = G.getVertex(s);

Dijkstra_shortest_Path(G, s, D, P);

cout<<"输出所有最短路径,格式（终点，最短路径长度，最短路径）\n";
stack<int> pathStack;
Type vertexdata;
for( i = 0; i<G.n(); i++){
if(i==s) continue;
vertexdata = G.getVertex(i);
if(D[i]>=100000){
cout <<"起点"<<sdata<<"到顶点"<<vertexdata
<<"没有路径\n";
continue;
}

for(int j = P[i];j!=s;j = P[j])

pathStack.push(j);
cout<<vertexdata<<" "<<D[i]<<" "<<sdata;

while(!pathStack.empty()){
int j = pathStack.top();
pathStack.pop();
cout<<G.getVertex(j);
}
cout<<G.getVertex(i)<<"\n";
}

delete[] D; delete[] P;
}