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

—图的创建和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-----

对于所有顶点v
  P(v) = v0;
  若存在弧<V0,V>，D(v) = arcs(V0,V)
  否则 D(v) = ∞

循环(直到找不到可加入S的顶点){
  在不在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.
#if !defined(AFX_GRAPH_H__C891E2F0_794B_4ADD_8772_55BA3
67C823E__INCLUDED_)
#define
AFX_GRAPH_H__C891E2F0_794B_4ADD_8772_55BA367C823E__I
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
// !defined(AFX_GRAPH_H__C891E2F0_794B_4ADD_8772_55BA367
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;
} 

赏

支付宝打赏

微信打赏

您的打赏是对我最大的鼓励！

Graph Creation and Dijkstra Algorithm

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

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

CATALOG

FEATURED TAGS

FRIENDS