2022年最短路径算法Dijkstra知识 .pdf

《2022年最短路径算法Dijkstra知识 .pdf》由会员分享，可在线阅读，更多相关《2022年最短路径算法Dijkstra知识 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最短路径算法Dijkstra 一、图的邻接表存储结构及实现（回顾）1头文件 graph.h/Graph.h:interface for the Graph class.#if!defined(AFX_GRAPH_H_C891E2F0_794B_4ADD_8772_55BA367C823E_INCLUDED_)#define AFX_GRAPH_H_C891E2F0_794B_4ADD_8772_55BA367C823E_INCLUDED_ 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 15 页 -#if _MSC_VER 1000#pragma once#endif/_MSC_

2、VER 1000#include#include using namespace std;#define NULL 0 typedef int weightType;typedef char Type;/数据元素类型classEdgeNode /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(i

3、nt vt1,int vt2,weightType w,EdgeNode*nxt=NULL)v1=vt1;v2=vt2;weight=w;next=nxt;/Constructor EdgeNode(EdgeNode*nxt=NULL)next=nxt;/Constructor;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 15 页 -typedef EdgeNode*Edge;struct VertexNode Type data;Edge first;VertexNode(Type d,Edge e):data(d),first(e);typedef VertexNode

4、Vertex;classGraph /Graph class:Adjacency list private:vector list;/The vertex list int numEdge;/Number of edges vector 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

5、 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 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 15 页 -int v2(Edge);/Return vertex edge goes to weightType weight(int,int);/Return weight of edge weightType weight(Edge);/Return

6、 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=0&ilist.size();return listi.data;void InsertVertex(const Type&vertexData);void InsertEdge(const int v1,const int v2,weightType weight);void RemoveVertex(c

7、onst 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_55BA367C823E_INCLUDED_)2cpp文件 graph.cpp/Graph.cpp:implementation of the Graph class.名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 15 页 -#include G

8、raph.h#define INFINITY 1000000 Graph:Graph()/Constructor numEdge=0;Graph:Graph()/Destructor:return allocated space/Remove all of the edges for(int v=0;vnext;delete temp;int Graph:n()return list.size();/Number of vertices int Graph:e()return numEdge;/Number of edges 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 15

9、页 -Edge Graph:first(int v)/Get the first edge for a vertex return listv.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

10、:v2(Edge w)return w-v2;/Vertex edge goes to weightType Graph:weight(int i,int j)/Return weight of edge for(Edge curr=listi.first;curr!=NULL;curr=curr-next)if(curr-v2=j)return curr-weight;return INFINITY;weightType Graph:weight(Edge w)/Return weight of edge 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 15 页 -if(w=N

11、ULL)return INFINITY;else return w-weight;bool Graph:getMark(int v)return Markv;void Graph:setMark(int v,bool val)Markv=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,weightTy

12、pe weight)Edge edge=new EdgeNode(v1,v2,weight);edge-next=listv1.first;listv1.first=edge;numEdge+;void Graph:RemoveVertex(const int v)void Graph:RemoveEdge(const int v1,const int v2)3测试程序 main.cpp 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 15 页 -#include#include#include Graph.h void main()Graph G;Type vdata;cout

13、vdata)G.InsertVertex(vdata);cin.clear();/置为正常状态int v1,v2;weightType weight;coutv1v2weight;while(v1=0&v2=0)G.InsertEdge(v1,v2,weight);coutv1v2weight;int i;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 15 页 -cout图中顶点数据为:;for(i=0;i G.n();i+)coutG.getVertex(i);coutendl;cout图中边数据为:;for(i=0;i G.n();i+)Edge edge=G.first(

14、i);while(edge)cout(v1 v2 weight);edge=G.next(edge);coutendl;二、Dijkstra 算法1Dijkstra 算法（Dijkstra_shortest_Path.cpp）：名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 15 页 -#include Graph.h#define INFINITY 1000000 const bool VISITED=true;const bool UNVISITED=false;/minVertex：在距离数组 D 中找最小的未加入S中的最短距离int minVertex(Graph&G,i

15、nt*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;iG.n();i+)/Initialize Di=INFINITY;Pi=s;Ds=0;G.setMark(s,VISITED);/add s to S for(Edge e=G.first(

16、s);G.isEdge(e);e=G.next(e)DG.v2(e)=G.weight(e);名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 15 页 -/在未加入 S 中的顶点中选择最短路径的那个顶点，/加入 S,并更新距离和路径数组for(i=0;i(Dv+G.weight(e)DG.v2(e)=Dv+G.weight(e);PG.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

17、 any unvisited vertex;for(int i=0;iG.n();i+)if(G.getMark(i)=UNVISITED)v=i;break;for(i+;iG.n();i+)/Now find smallest D value 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 15 页 -if(G.getMark(i)=UNVISITED)&(Di Dv)v=i;return v;2修改后的测试程序：#include#include#include Graph.h void main()Graph G;Type vdata;coutvdata)G.Insert

18、Vertex(vdata);cin.clear();/置为正常状态int v1,v2;weightType weight;coutv1v2weight;名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 15 页 -while(v1=0&v2=0)G.InsertEdge(v1,v2,weight);coutv1v2weight;int i;cout图中顶点数据为:;for(i=0;i G.n();i+)coutG.getVertex(i);coutendl;cout图中边数据为:;for(i=0;i G.n();i+)Edge edge=G.first(i);while(edge

19、)cout(v1 v2 weight);edge=G.next(edge);coutendl;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 15 页 -/Dijkstra_shortest_Path算法weightType*D=new weightTypeG.n();int*P=new intG.n();int s;couts;Type sdata=G.getVertex(s);Dijkstra_shortest_Path(G,s,D,P);cout输出所有最短路径,格式（终点，最短路径长度，最短路径）n;stack pathStack;Type vertexdata;for

20、(i=0;i=100000)cout 起点sdata到顶点 vertexdata 没有路径 n;continue;for(int j=Pi;j!=s;j=Pj)名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 15 页 -pathStack.push(j);coutvertexdata Di sdata;while(!pathStack.empty()int j=pathStack.top();pathStack.pop();coutG.getVertex(j);coutG.getVertex(i)n;delete D;delete P;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 15 页 -