c++ dijkstra’s算法
2017-08-11 15:23:34 xll1314521 阅读数 289

Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。 Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
Dijkstra 算法的时间复杂度为O(n^2)   
空间复杂度取决于存储方式,邻接矩阵为O(n^2)
代码实现

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
#define INF 0x7fffffff
#define maxN 50
#define USE_C 1
#define NOT_USE_C 0
#define USE_CPP 1
int matrix[maxN][maxN];
void Dijkstra_cpp(vector<vector<int>>&vec,vector<int>& result,int v0){
    vector<int> visited(vec.size(),0);
    int last_visitied = 0;
    result[0] = 0;
    for(int i =0;i<vec.size()-1;i++){
        for(int j = 0;j<vec.size()-1;j++){
        if(visited[i]==0){
            if(vec[v0][j]!= 0){
            int dist =vec[v0][j] +last_visited;
            if(dist<result[j])
            result[j] = dist;
        }
    }
}
    int minIndex = 0;
    while(visited[minIndex] == 1)
        minIndex++;
    for(int j = minIndex;j<vec.size();j++){
        if(visited[j] ==0&&result[j]<result[minIndex]){
            minIndex = j;
        }
    }
    last_visited = result[minIndex];
    visited[minIndex] = 1;
    v0 = minIndex;
    }
} 
int _tmain(int argc,_TCHAR* argv[]){
    freopen("Dijkstra2Data.txt","r",stdin);
    int n;
    cin>>n;
    vector<vector<int>> vec(n,vector<int>(n,0));
    for(i = 0;i<n;i++){
        for(j = 0;j<n;j++){
            cin>>vec[i][j];
        }
    }
    vector<int> result(n,INF);
    Dijkstra_cpp(vec,result,0);
    for(int i  =0;i<n;i++){
        if(result[i] == INF)
        cout<<"INF"<<endl;
        else
        cout<<result[i]<<endl;
    }
    return 0;
}
2014-04-22 15:43:35 Rover1234 阅读数 512

Dijkstra算法描述为:假设用带权邻接矩阵来表示带权有向图。首先引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点Vi的最短路径。它的初始状态为:若两顶点之间有弧,则D[i]为弧上的权值;否则置D[i]为无穷大。

(1)找到与源点v最近的顶点,并将该顶点并入最终集合S

(2)根据找到的最近的顶点更新从源点v出发到集合V-S上可达顶点的最短路径距离;

(3)重复以上操作。

以下图中所示的带权有向图为例:

#include <iostream>
#include <sstream>
#define INFINITY  32767
#define VERTEX_NUM 6  //顶点个数

//Dijkstra算法。
//adjMatrix为有向网的带权邻接矩阵。v0为源点。pathMatrix[v][w]为true则v0到v经过w。D[v]为v0到v的距离。
void 
Dijkstra(int adjMatrix[][VERTEX_NUM],int v0,bool pathMatrix[][VERTEX_NUM],int D[])
{
  bool final[VERTEX_NUM];//final[v]=true,则v属于集合S

  for(int v=0;v<VERTEX_NUM;v++)//
  {
    final[v]=false;
    D[v]=adjMatrix[v0][v];
    for(int w=0;w<VERTEX_NUM;w++)
      pathMatrix[v][w]=false;//设空路径
    if(D[v]<INFINITY)
    {
      pathMatrix[v][v0]=true;
      pathMatrix[v][v]=true; 
    }
  }
  pathMatrix[v0][v0]=true;
  D[v0]=0;
  final[v0]=true;//初始化v0属于S集
  
  //开始主循环,每次求得v0到某个顶点v的最短路径,并加v到S
  for(int i=1;i<VERTEX_NUM;i++)//其余VERTEX_NUM-1个顶点
  {
    int minDistance=INFINITY;
    int v;
    for(int w=0;w<VERTEX_NUM;w++)
    { 
      if(final[w]==false)
        if(D[w]<minDistance)
        {
          minDistance=D[w];
          v=w;
        }
    }
    final[v]=true;//v加入S
	
    //更新当前最短路径及距离
    for(int w=0;w<VERTEX_NUM;w++)
    {
      if(final[w]==false&&(minDistance+adjMatrix[v][w]<D[w]))
      {
        D[w]=minDistance+adjMatrix[v][w];
        pathMatrix[w][v]=true;
        pathMatrix[w][w]=true;
      }
    }
  }
}

int main()
{
  //adjMatrix为有向网的带权邻接矩阵。
  int adjMatrix[VERTEX_NUM][VERTEX_NUM]
  ={{INFINITY ,INFINITY ,10 ,INFINITY ,30 ,100 },
    {INFINITY ,INFINITY ,5 ,INFINITY ,INFINITY ,INFINITY },
    {INFINITY ,INFINITY ,INFINITY ,50 ,INFINITY ,INFINITY },
    {INFINITY ,INFINITY ,INFINITY ,INFINITY ,INFINITY ,10 },
    {INFINITY ,INFINITY ,INFINITY ,20 ,INFINITY ,60 },
    {INFINITY ,INFINITY ,INFINITY ,INFINITY ,INFINITY ,INFINITY }};

  bool pathMatrix[VERTEX_NUM][VERTEX_NUM];//pathMatrix[v][w]为true则v0到v经过w。
  int D[VERTEX_NUM];//D[v]为v0到v的距离。
  int vSource=0;//源点
  Dijkstra( adjMatrix,vSource,pathMatrix,D );

  for(int i=0;i<VERTEX_NUM;i++)
  {
    if(vSource==i) continue;
    std::string pathPoint;//源点到其他点的路径点
    for(int j=0;j<VERTEX_NUM;j++)
    {
      if(pathMatrix[i][j])
      {
        std::stringstream ss;//为了将int转为string
        std::string strJ;
        ss<<j;
        ss>>strJ;
        pathPoint+=" v"+strJ;
      } 
    }
    std::cout<<"v0 to v"<<i<<"    distance: "<<D[i]<<"    path point: "<<pathPoint<<std::endl; 
  }
  return 0;
}

输出结果为:


2018-11-30 21:04:37 majinlei121 阅读数 240

单源最短路径算法 dijkstra
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
(1)从起始节点0开始,与0连接的节点有1,2,3,将它们的权重存入右表中,可以看出最小的权重是边0-2,权重为2,那么在图中不能有负权边的前提下,0-2的最短路径就是边0-2
在这里插入图片描述
(2)接下来,以节点2为出发点,考察与2连接的节点1,4,3,边2-1的权重为1,那么0-2-1的耗费为3,比上图表中0-1的耗费5要小,所以将1位置的5替换为3;边2-4权重为5,表中没有4的耗费,那么0-2-4的耗费7填入表中;边2-3权重为3,那么0-2-3耗费为5,比表中0-3的耗费6要小,那么将上图表中3对应的耗费6改为耗费5,如下图
在这里插入图片描述
(3)在上面的基础上,我们可以确定0到1最短的路径是0-2-1,耗费为3,因此节点1也确定下来了,标记为蓝色,表格中节点1对应的耗费3标为红色
在这里插入图片描述
(4)此时节点2的邻边都遍历完了,确定了节点1为最短路径,此时将节点1固定住,将节点1作为出发点,节点1的邻边只有一个4, 0-2-1-4的耗费为4,比原来的7小,所以将7替换为4,此时节点1的邻边都遍历完了,确定节点4为最短路径,标记为蓝色,表格中节点4对应的耗费4标红
在这里插入图片描述
(5)此时节点4没有相邻的节点,剩下的节点3也没有别的选择了,0-2-3就是最短路径,如下图
在这里插入图片描述
程序实现如下

#include <iostream>
#include "SparseGraph.h"
#include "ReadGraph.h"
#include "Dijkstra.h"

using namespace std;

int main()
{
    string filename = "testG1.txt";
    int V = 5;

    SparseGraph<int> g = SparseGraph<int>(V, true);
    ReadGraph<SparseGraph<int>, int> readGraph( g, filename );

    cout<<"Test Dijkstra:"<<endl<<endl;
    Dijkstra<SparseGraph<int>, int> dij(g, 0);
    for( int i = 1; i < V; i ++){
        cout<<"Shortest Path to "<<i<<" : "<<dij.shortestPathTo(i)<<endl;
        dij.showPath(i);
        cout<<"---------"<<endl;
    }

    return 0;
}

Dijkstra.h

#include <iostream>
#include <vector>
#include <stack>

#ifndef _EDGE_H_
#define _EDGE_H_
#include "Edge.h"
#endif

#ifndef _INDEXMINHEAP_H_
#define _INDEXMINHEAP_H_
#include "IndexMinHeap.h"
#endif

using namespace std;

template<typename Graph, typename Weight>
class Dijkstra{

private:
    Graph &G;
    int s;

    Weight *distTo;
    bool *marked;
    vector< Edge<Weight>* > from;

public:
    Dijkstra(Graph &graph, int s):G(graph){
        this->s = s;
        distTo = new Weight[G.V()];
        marked = new bool[G.V()];
        for ( int i = 0; i < G.V(); i ++){
            distTo[i] = Weight();
            marked[i] = false;
            from.push_back(NULL);
        }

        IndexMinHeap<Weight> ipq(G.V());

        // Dijkstra
        distTo[s] = Weight();
        ipq.insert( s, distTo[s] );
        marked[s] = true;

        while ( !ipq.isEmpty() ){

            int v = ipq.extractMinIndex();

            //distTo[v] 就是s到v的最短距离
            marked[v] = true;

            typename Graph::adjIterator adj(G, v);
            for( Edge<Weight>* e = adj.begin(); !adj.end(); e = adj.next() ){
                int w = e->other(v);
                if ( !marked[w] ){
                    if ( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
                        distTo[w] = distTo[v] + e->wt();
                        from[w] = e;
                        if ( ipq.contain(w) )
                            ipq.change( w, distTo[w] );
                        else
                            ipq.insert( w, distTo[w]);
                    }
                }
            }
        }
    }

    ~Dijkstra(){
        delete[] distTo;
        delete[] marked;
    }

    Weight shortestPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return distTo[w];
    }

    bool hasPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return marked[w];
    }

    void shortestPath( int w, vector< Edge<Weight> > &vec){
        assert( w >= 0 && w < G.V() );

        stack< Edge<Weight>* > s;
        Edge<Weight> *e = from[w];

        while( e->v() != this->s ){
            s.push(e);
            e = from[e->v()];
        }
        s.push(e);

        while( !s.empty() ){
            e = s.top();
            vec.push_back( *e );
            s.pop();
        }
    }

    void showPath( int w ){
        assert( w >= 0 && w < G.V() );

        vector< Edge<Weight> > vec;
        shortestPath(w, vec);
        for ( int i = 0; i < vec.size(); i ++ ){
            cout<<vec[i].v()<<" -> ";
            if ( i == vec.size() - 1 )
                cout<<vec[i].w()<<endl;
        }
    }
};

其他的函数见上几篇博客

testG1.txt 为

5 8
0 1 5
0 2 2
0 3 6
1 4 1
2 1 1
2 4 5
2 3 3
3 4 2

输出为
在这里插入图片描述

2017-05-08 19:25:41 weixin_38044916 阅读数 351
#include<iostream>
#include <windows.h>
#define MAX 9
using namespace std;
//网图类
template<class Type>
class NetGraph
{
private:
    Type vexs[MAX];//顶点表
    int arc[MAX][MAX];//邻接矩阵
    int numVertexes;//当前网中顶点数
    int numEdges;//当前网中边数

    int getPosition(Type el);//获取el在顶点表中的位置
public:
    NetGraph();//创建一个网
    //~NetGraph();//析构函数
    void print();//打印邻接矩阵
    void ShortestPath_Dijkstra(int v0, int *P, int *D);//迪杰斯特拉(Dijkstra)算法
};
//获取el在顶点表中的位置
template<class Type>
int NetGraph<Type>::getPosition(Type el)
{
    int i;
    for (i = 0; i < this->numVertexes; i++)
    {
        if (this->vexs[i] == el)
            return i;
    }
    return -1;
}
//创建一个网,手动输入
template<class Type>
NetGraph<Type>::NetGraph()
{
    Type c1, c2;
    int p1, p2;
    int i, j;
    int weight;//权值
    cout << "Input Vertexes number: ";
    cin >> this->numVertexes;
    cout << "Input Edges number: ";
    cin >> this->numEdges;
    //检测顶点和边数输入的合法性
    if (this->numVertexes < 1 || this->numEdges<1 || this->numEdges>this->numVertexes*(this->numVertexes - 1))
    {
        cout << "Input invalid!" << endl;
        return;
    }
    //初始化顶点
    for (i = 0; i < this->numVertexes; i++)
    {
        cout << "Input a Type data(" << i + 1 << "): ";
        cin >> this->vexs[i];
    }
    //初始化边
    for (i = 0; i < this->numVertexes; i++)
    {
        for (j = 0; j < this->numVertexes; j++)
        {
            if (i == j)
                this->arc[i][j] = 0;
            else
                this->arc[i][j] = 65535;
        }
    }
    for (i = 0; i < this->numEdges; i++)
    {
        cout << "Input a arc:  ";
        cin >> c1;
        cout << "Input a arc:  ";
        cin >> c2;

        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1 || p1 == p2)
        {
            cout << "Input Egde error!" << endl;
            return;
        }
        cout << "Input a weight: ";
        cin >> weight;
        this->arc[p1][p2] = weight;
        this->arc[p2][p1] = weight;
    }
}
//打印邻接矩阵
template<class Type>
void NetGraph<Type>::print()
{
    int i, j;
    cout << "***********************************" << endl;
    cout << "邻接矩阵:" << endl;
    for (i = 0; i < this->numVertexes; i++)
    {
        for (j = 0; j < this->numVertexes; j++)
            cout << this->arc[i][j] << "\t";
        cout << endl;
    }
}
//迪杰斯特拉(Dijkstra)算法
template<class Type>
void NetGraph<Type>::ShortestPath_Dijkstra(int v0, int *P, int *D)
{
    int v, w, k, min;
    int final[MAX];//final[w]=1表示求得顶点v0至vw的最短路径
    for (v = 0; v < this->numVertexes; v++)
    {
        final[v] = 0;//全部顶点初始化为未知最短路径状态
        D[v] = this->arc[v0][v];//将与v0点有连线的顶点上加上权值
        P[v] = 0;//初始化路径数组P为0
    }
    final[v0] = 1;//v0至v0不需要求路径
    D[v0] = 0;//v0至v0权值为0
    //开始主循环,每次求得v0到某个v顶点的最短路径
    for (v = 1; v < this->numVertexes; v++)
    {
        min = 65535;
        for (w = 0; w < this->numVertexes; w++)
        {
            if (!final[w] && D[w] < min)
            {
                k = w;//保存
                min = D[w];
            }
        }
        final[k] = 1;
        for (w = 0; w < this->numVertexes; w++)
        {
            if (!final[w] && (min + this->arc[k][w] < D[w]))
            {
                D[w] = min + this->arc[k][w];
                P[w] = k;
            }
        }
    }
}


int main()
{
    int i;
    int P[MAX], D[MAX];
    NetGraph<char> graph;
    graph.print();
    graph.ShortestPath_Dijkstra(0, P, D);
    cout << "*********************" << endl;
    for (i = 0; i < MAX; i++)
        cout << D[i] << " ";
    cout << endl;
    cout << "*********************" << endl;
    for (i = 0; i < MAX; i++)
        cout << P[i] << " ";
    cout << endl;
    system("pause");
    return 0;
}
2016-08-28 18:47:59 chengonghao 阅读数 4695

Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,是广度优先算法的一种,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。其基本原理是:每次新扩展一个距离最短的点,更新与其相邻的点的距离。当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。 Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。   Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。

Dijkstra 算法的时间复杂度为O(n^2)   空间复杂度取决于存储方式,邻接矩阵为O(n^2)

先上代码:

// Dijkstra.cpp : 定义控制台应用程序的入口点。
//

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace::std;

#define INF 0x7fffffff
#define maxN 50
#pragma warning(disable:4996)

#define USE_C 1
#define NOT_USE_C 0

#define USE_CPP 1

int matrix[maxN][maxN];
// C++实现
void Dijkstra_cpp(vector<vector<int>>&vec, vector<int>& result, int v0){
	vector<int> visited(vec.size(), 0); // 表示顶点是否被选中,0:顶点未被选中;1:顶点已被选中
	int last_visited = 0;
	visited[v0] = 1; // 选中起始顶点
	result[0] = 0;

	for (int i = 0; i < vec.size() - 1; ++i) { // N 个顶点需要做 N - 1 次循环
		// 查看顶点周围的所有点
		for (int j = 0; j < vec.size(); ++j) { // 循环遍历所有顶点
			if (visited[j] == 0){ // 保证被查看的新顶点没有被访问到
				if (vec[v0][j] != 0){ // 保证当前顶点(V0)与新顶点(j)之间有路径
					int dist = vec[v0][j] + last_visited; // 计算 V0 到 J 的路径距离
					if (dist < result[j])result[j] = dist; // 用新路径代替原来的路径
				}
			}
		}
		// 找出最小值
		int minIndex = 0;
		while (visited[minIndex] == 1) minIndex++; // 找第一个没有被选中的节点
		for (int j = minIndex; j < vec.size(); ++j) {
			if (visited[j] == 0 && result[j] < result[minIndex]){
				minIndex = j;
			}
		}

		last_visited = result[minIndex]; // 更新最小值
		visited[minIndex] = 1; // 将最小值顶点选中
		v0 = minIndex; // 下次查找从最限制顶点开始
	}
}
// C语言实现
void Dijkstra_c(int out[], int N, int v0){
	int i, j;
	int visited[maxN] = { 0 }; // 表示顶点是否被选中,0:顶点未被选中;1:顶点已被选中
	int last_visited = 0;
	for (i = 0; i < N; ++i){
		out[i] = INF; // 把输出结果全部初始化为无穷大
	}
	visited[v0] = 1; // 选中起始顶点
	out[v0] = 0;

	for (i = 0; i < N - 1; ++i) { // N 个顶点需要做 N - 1 次循环
		// 查看顶点周围的所有点
		for (j = 0; j < N; ++j) { // 循环遍历所有顶点
			if (visited[j] == 0) { // 保证被查看的新顶点没有被访问到
				if (matrix[v0][j] != 0){ // 保证当前顶点(V0)与新顶点(j)之间有路径
					int dist = matrix[v0][j] + last_visited; // 计算 V0 到 J 的路径距离
					if (dist < out[j])out[j] = dist; // 用新路径代替原来的路径
				}
			}
		}
		// 找出最小值
		int minIndex = 0;
		while (visited[minIndex] == 1) minIndex++; // 找第一个没有被选中的节点
		for (j = minIndex; j < N; ++j) {
			if (visited[j] == 0 && out[j] < out[minIndex]){
				minIndex = j;
			}
		}

		last_visited = out[minIndex]; // 更新最小值
		visited[minIndex] = 1; // 将最小值顶点选中
		v0 = minIndex; // 下次查找从最限制顶点开始
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
#if 0
	freopen("Dijkstra2Data.txt", "r", stdin);
	int result[maxN];
	int N, i, j;
	scanf("%d", &N);
	for (i = 0; i < N; ++i){
		for (j = 0; j < N; ++j){
			scanf("%d", &matrix[i][j]);
		}
	}

	Dijkstra_c(result, N, 0);

	for (i = 0; i < N; ++i){
		if (result[i] == INF)printf("INF\n");
		else printf("%d\n", result[i]);
	}
#endif

	freopen("Dijkstra2Data.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	vector<vector<int>> vec(n, vector<int>(n, 0));
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> vec[i][j];
		}
	}

	vector<int> result(n, INF); // 把输出结果全部初始化为无穷大
	Dijkstra_cpp(vec,result, 0);

	for (int i = 0; i < n; ++i){
		if (result[i] == INF)printf("INF\n");
		else printf("%d\n", result[i]);
	}
	return 0;
}


假设我们的测试用例如下图所示:


我们以A作为起始顶点,计算A到每个顶点的最短路径,注意,这是一幅带权图,图的邻接矩阵表示如下:


计算结果如下:


没有更多推荐了,返回首页