天天看点
返回

单源最短路径问题（Dijkstra算法）

文章目录

      • 一、介绍
      • 二、实战
      • 三、时间复杂度
      • 四、用优先队列优化
      • 最小堆
无向图 单源最短路径 Dijkstra算法 最小堆

一、介绍

算法描述

二、实战

单源最短路径问题（Dijkstra算法）

(图片来源未知)

求上图从Start到Destination的最短路径
  • python解法 
INF = 1e10        # 无限大
node_number = 16  # node的数目
route_length = [  # node节点间的距离矩阵
[INF,   4, INF,   2, INF, INF,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 节点0
[  4, INF,   2, INF,   7,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 节点1
[INF,   2, INF,   5, INF,   2, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 节点2
[  2, INF,   5, INF, INF, INF, INF,   8, INF, INF, INF, INF, INF, INF, INF, INF], # 节点3
[INF,   7, INF, INF, INF,   5, INF, INF, INF, INF,   6, INF,   8, INF,   9, INF], # 节点4
[INF,   3,   2, INF,   5, INF, INF, INF,   3, INF,   9, INF, INF, INF, INF, INF], # 节点5
[  3, INF, INF, INF, INF, INF, INF,   5,   4,   7, INF, INF, INF, INF, INF, INF], # 节点6
[INF, INF, INF,   8, INF, INF,   5, INF, INF,   1, INF,   8, INF, INF, INF, INF], # 节点7
[INF, INF, INF, INF, INF,   3,   4, INF, INF, INF,   4, INF, INF, INF, INF, INF], # 节点8
[INF, INF, INF, INF, INF, INF,   7,   1, INF, INF,   4, INF, INF, INF, INF, INF], # 节点9
[INF, INF, INF, INF,   6,   9, INF, INF,   4,   4, INF,   4, INF,   7, INF, INF], # 节点10
[INF, INF, INF, INF, INF, INF, INF,   8, INF, INF,   4, INF, INF,   2, INF, INF], # 节点11
[INF, INF, INF, INF,   8, INF, INF, INF, INF, INF, INF, INF, INF,   8, INF,   9], # 节点12
[INF, INF, INF, INF, INF, INF, INF, INF, INF, INF,   7,   2,   8, INF,   4,   8], # 节点13
[INF, INF, INF, INF,   9, INF, INF, INF, INF, INF, INF, INF, INF,   4, INF,   3], # 节点14
[INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF,   9,   8,   3, INF]] # 节点15
cost = [INF] * node_number    # 从起点到各个节点间的距离初始化为INF
pre_node= [0] * node_number   # 记录索引对应节点的上一个节点（方便打印路径）

cost[0]=0  # cost of start to start is 0. After that, cost is: [0,INF,INF,...INF]
L = [i for i in range(node_number)]  # list of node.

while L:
    minimum=INF
    min_cost_node=0
    for i in L:  # find the index of the node which has the minimum cost in list 'cost'.
        if minimum>cost[i] and i!=-1:  # i=-1 means that node 'i' is deleted in the previous loop.
            minimum=cost[i]
            min_cost_node=i
    if min_cost_node==15:   # 15 is the end node we want to go.
        break
    L[min_cost_node]=-1  # delete the node in list 'L'
    for index,val in enumerate(route_length[min_cost_node]):  # route_length[min_cost_node] is one row of the matrix.
        '''
        For example,when min_cost_node is node '0',
        then the row is [INF,   4, INF,   2, INF, INF,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF]. # ノード0
        in this 'for' loop, (index,val) can be (0,INF),(1,4),(2,INF),(3,2)...(15,INF). 
        '''
        if val<INF:    # val<INF means that I can directly go to node 'index' from node 'min_cost_node'.
            if cost[index]>cost[min_cost_node]+val:
                '''
                Update the list 'cost'.Because we find a path 
                which go through node 'min_cost_node' costs fewer then the path found previously.
                '''
                cost[index] = cost[min_cost_node] + val
                '''
                Because this path has a road from node 'min_cost_node' to node 'index',
                we record this road.Just let node 'min_cost_node' be the previous node of node 'index'.
                '''
                pre_node[index]=min_cost_node

# path is the result we find.
path=[]
vertex=15
while vertex!=0:
    path.append(vertex)
    vertex=pre_node[vertex]
path.append(0)
print('The minimum cost path is: ')
for i in range (len(path)-1,0,-1):
    print(path[i],'-->',end='')
print(path[0])
print('The cost is: ',cost[15])
单源最短路径问题（Dijkstra算法）
  • C++解法
    • 主要函数： 
/*
计算从节点's'开始的最短路径
结果存储在数组D中
*/
void Dijkstra(graph* G, int* D, int s) {
	int i, v, w;
	for (i = 0; i < G->n(); ++i) {
		v = minVertex(G, D);
		if (D[v] == INF)
			return; //说明节点v是孤立点，不可到达
		G->setMark(v, VISITED);
		for (w = G->first(v); w < G->n(); w = G->next(v, w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				/*顶点w的上一个顶点是v*/
				path[w] = v;
			}
	}
}
  • 完整代码
主函数所在文件 
#include<iostream>
#include<stack>
#include "graphm.h"
#include<string.h>
const int INF = 1e8;
const int VISITED = 1;
const int N = 16;
int path[1000];
int D[N];
/*找到当前花费最小的顶点*/
int minVertex(graph* G, int* D) {
	int i, v = -1;
	/*从头开始，找到一个没有被访问过的顶点，赋值给v*/
	for(i=0;i<G->n();++i)
		if (G->getMark(i) == UNVISITED) { v = i; break; }
	/*与上面的顶点比较花费大小，找到花费最小的未被访问的顶点*/
	for (i++; i < G->n(); i++)
		if (G->getMark(i) == UNVISITED && (D[i] < D[v]))
			v = i;
	return v;
}

/*
计算从节点's'开始的最短路径
结果存储在数组D中
*/
void Dijkstra(graph* G, int* D, int s) {
	int i, v, w;
	for (i = 0; i < G->n(); ++i) {
		v = minVertex(G, D);
		if (D[v] == INF)
			return; //说明节点v是孤立点，不可到达
		G->setMark(v, VISITED);
		for (w = G->first(v); w < G->n(); w = G->next(v, w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				/*顶点w的上一个顶点是v*/
				path[w] = v;
			}
	}
}

int main() {
	int matrix[N][N] = {// node节点间的距离矩阵
		{INF, 4, INF, 2, INF, INF, 3, INF, INF, INF, INF, INF, INF, INF, INF, INF} , // 节点0
			{4, INF, 2, INF, 7, 3, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}, // 节点1
			{INF, 2, INF, 5, INF, 2, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}, // 节点2
			{2, INF, 5, INF, INF, INF, INF, 8, INF, INF, INF, INF, INF, INF, INF, INF}, // 节点3
			{INF, 7, INF, INF, INF, 5, INF, INF, INF, INF, 6, INF, 8, INF, 9, INF}, // 节点4
			{INF, 3, 2, INF, 5, INF, INF, INF, 3, INF, 9, INF, INF, INF, INF, INF}, // 节点5
			{3, INF, INF, INF, INF, INF, INF, 5, 4, 7, INF, INF, INF, INF, INF, INF}, // 节点6
			{INF, INF, INF, 8, INF, INF, 5, INF, INF, 1, INF, 8, INF, INF, INF, INF}, // 节点7
			{INF, INF, INF, INF, INF, 3, 4, INF, INF, INF, 4, INF, INF, INF, INF, INF}, // 节点8
			{INF, INF, INF, INF, INF, INF, 7, 1, INF, INF, 4, INF, INF, INF, INF, INF}, // 节点9
			{INF, INF, INF, INF, 6, 9, INF, INF, 4, 4, INF, 4, INF, 7, INF, INF}, // 节点10
			{INF, INF, INF, INF, INF, INF, INF, 8, INF, INF, 4, INF, INF, 2, INF, INF}, // 节点11
			{INF, INF, INF, INF, 8, INF, INF, INF, INF, INF, INF, INF, INF, 8, INF, 9}, // 节点12
			{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 7, 2, 8, INF, 4, 8}, // 节点13
			{INF, INF, INF, INF, 9, INF, INF, INF, INF, INF, INF, INF, INF, 4, INF, 3}, // 节点14
	       {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 9, 8, 3, INF}// 节点15
	}; 
	memset(path, -1, sizeof(path));
	graph* G = new graphm(N);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			G->setEdge(i, j, matrix[i][j]);
	for (int i = 0; i < N; ++i)
		D[i] = INF;
	D[0] = 0;          //顶点和顶点自己之间的距离为0
	Dijkstra(G, D, 0);
	std::cout << "从起点到终点的最短路径是： ";
	int prev = N - 1;
	std::stack<int>pth;
	while (path[prev] != -1) {
		pth.push(path[prev]);
		prev = path[prev];
	}
	while (!pth.empty()) {
		std::cout << pth.top() << " --> ";
		pth.pop();
	}
	std::cout <<N-1<< std::endl;
	std::cout <<"总距离为： "<< D[N - 1] << std::endl;
}
文件2：graph.h(图的抽象类) 
#pragma once
/*程序代码源于《数据结构与算法C++描述第三版》*/

/*
图的抽象类，这里假设图被创建后，图的顶点数目不变
*/
class graph
{
private:
	void operator=(const graph&) {}    //保护图，防止图被显示赋值
	graph(const graph&) {}       //复制构造函数也设为私有
public:
	graph() {}         //默认构造函数
	virtual ~graph() {}  //析构函数

	//初始化有n个节点的图
	virtual void Init(int n) = 0;

	//返回图的顶点数目和边的数目
	virtual int n() = 0;
	virtual int e() = 0;

	//返回顶点'v'的第一个相邻顶点
	virtual int  first(int v) = 0;

	//返回顶点v的下一个相邻顶点（在顶点'w'之后）
	virtual int next(int v, int w) = 0;

	//设置边的权重，i,j是顶点，wgt是边的权重
	virtual void setEdge(int i, int j, int wgt)=0;

	//删除边，i,j是顶点
	virtual void delEdge(int i, int j) = 0;

	//判断边是否在图中，i,j是顶点,如果边（i,j）权重不为0返回true
	virtual bool isEdge(int i, int j) = 0;

	//返回边的权重，i,j是顶点，
	virtual int weight(int i, int j) = 0;

	//获取或者设置顶点'v'的标志值，方便确认这个顶点之前是否被我们访问过
	//val是要设置的值
	virtual int getMark(int v) = 0;
	virtual void setMark(int v, int val) = 0;
};
文件3：graphm.h(图的相邻矩阵实现) 
#pragma once
#include"graph.h"
const int UNVISITED = 0;
class graphm: public graph
{
private:
	int numVertex, numEdge;   //顶点和边的数目
	int** matrix;             //相邻矩阵
	int* mark;				  //标记数组
public:
	graphm(int numVert) {     //构造函数
		Init(numVert);
	}
	~graphm()   //析构函数
	{
		delete[]mark;
		for (int i = 0; i < numVertex; ++i)
			delete[]matrix[i];
		delete []matrix;
	}

	//初始化有n个顶点的图
	void Init(int n) {
		int i;
		numVertex = n;
		numEdge = 0;
		mark = new int[n];
		//初始化标记数组
		for (i = 0; i < numVertex; ++i)
			mark[i] = UNVISITED;
		matrix = new int* [numVertex];
		for (i = 0; i < numVertex; ++i)
			matrix[i] = new int[numVertex];
		for (i = 0; i < numVertex; ++i)
			for (int j = 0; j < numVertex; ++j)
				matrix[i][j] = 0;    //0代表边不存在
	}

	//顶点数目
	int n() { return numVertex; }
	
	//边的数目
	int e() { return numEdge; }

	//返回顶点'v'的第一个相邻顶点
	int  first(int v) {
		for (int i = 0; i < numVertex; ++i)
			if (matrix[v][i] != 0)return i;
		return numVertex;     //代表这个点是孤立点
	}

	//返回顶点v的下一个相邻顶点（在顶点'w'之后）
	int next(int v, int w) {
		for (int i = w + 1; i < numVertex; ++i)
			if (matrix[v][i] != 0)return i;
		return numVertex;      //没有下一个顶点
	}

	//设置边的权重，i,j是顶点，wgt是边的权重
	void setEdge(int i, int j, int wgt) {
		if (wgt <= 0)return;
		if (matrix[i][j] == 0)++numEdge;
		matrix[i][j] = wgt;
	}

	//删除边，i,j是顶点
	void delEdge(int i, int j) {
		if (matrix[i][j] != 0)--numEdge;
		matrix[i][j] = 0;
	}

	//判断边是否在图中，i,j是顶点,如果边（i,j）权重不为0返回true
	bool isEdge(int i, int j) {
		return matrix[i][j] != 0;
	}

	//返回边的权重，i,j是顶点，
	int weight(int i, int j) { return matrix[i][j]; }

	//获取或者设置顶点'v'的标志值，方便确认这个顶点之前是否被我们访问过
	//val是要设置的值
	int getMark(int v) { return mark[v]; }
	void setMark(int v, int val) { mark[v] = val; }
};

三、时间复杂度

  • 上面C++代码 (和python的解法是完全一样的) 的时间复杂度为 Θ ( ∣ V ∣ 2 + ∣ E ∣ ) = Θ ( ∣ V ∣ 2 ) \Theta(|V|^2+|E|)=\Theta(|V|^2) Θ(∣V∣2+∣E∣)=Θ(∣V∣2)
    • 说明：因为每次扫描需要进行 ∣ V ∣ |V| ∣V∣次（外层for循环），在整个外层for循环中，判断并更新数组D需要进行 ∣ E ∣ |E| ∣E∣次，也就是每条边都被访问有且仅有一次。在内层for循环中，查找minVertex需要 Θ ( ∣ V ∣ ) \Theta(|V|) Θ(∣V∣)的时间，所以总共需要 Θ ( ∣ V ∣ 2 + ∣ E ∣ ) \Theta(|V|^2+|E|) Θ(∣V∣2+∣E∣)的时间，又因为 ∣ E ∣ < ∣ V ∣ 2 |E|<|V|^2 ∣E∣<∣V∣2，故总的时间开销是： Θ ( ∣ V ∣ 2 ) \Theta(|V|^2) Θ(∣V∣2)

四、用优先队列优化

上面C++寻找minVertex的过程可以优化，下面代码运行没有问题，输出结果和上面的一样。时间复杂度是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)
  • 说明：这种方法是把未处理的顶点按照距离值大小顺序保存在一个最小堆中，每次修改完D(w)的值后，将这个新的距离值和顶点作为一个新的元素添加到堆中。一个顶点当前在堆中的最小值会被优先找到，而其后的较大值将会被忽略，因为此时顶点已被标记为VISITED。
  • 在最差情况下，堆中的元素数目会由 ∣ V ∣ |V| ∣V∣增加到 ∣ E ∣ |E| ∣E∣,这样每次插入需要 O ( l o g 2 ∣ E ∣ ) O(log_2|E|) O(log2​∣E∣)的时间复杂度，虽然有两层for循环，如果从边的数目出发，会发现每条边最多被访问一次，这样总的时间复杂度是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣),至于那个do,while循环，它用的总时间也是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)的，因为它每进行一次循环，都会移走一个顶点，最多有 ∣ E ∣ |E| ∣E∣个顶点，所以最多进行 ∣ E ∣ |E| ∣E∣次循环，而每次循环，里面的 r e m o v e f i r s t ( ) removefirst() removefirst()的时间复杂度是 O ( l o g 2 ∣ E ∣ ) O(log_2|E|) O(log2​∣E∣)的，相乘，即得出 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)，所以最终的时间复杂度是： O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣) 
/*程序代码源于《数据结构与算法C++描述第三版》*/

class DijkElem {
public:
	int vertex, distance;
	DijkElem() { vertex = -1; distance = -1; }
	DijkElem(int v, int d) { vertex = v; distance = d; }
};
class DDComp {
public:
	static bool prior(DijkElem a, DijkElem b) {
		return (a.distance < b.distance);
	}
};

/*用优先队列实现Dijkstra算法*/
void Dijkstra2(graph* G, int* D, int s) {
	/*v是当前的minVertex*/
	int i, v, w;
	DijkElem temp;
	DijkElem *E=new DijkElem[G->e()];
	temp.distance = 0;
	temp.vertex = s;
	E[0] = temp;
	heap<DijkElem, DDComp>H(E, 1, G->e());
	for (int i = 0; i < G->n(); ++i) {
		do {
			if (H.size() == 0)return;
			temp = H.removefirst();
			v = temp.vertex;
		} while (G->getMark(v) == VISITED);
		G->setMark(v, VISITED);
		if (D[v] == INF)return;    //说明节点v是孤立点，不可到达
		for(w=G->first(v);w<G->n();w=G->next(v,w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				path[w] = v;
				temp.distance = D[w];
				temp.vertex = w;
				/*在最小堆中插入新的节点（距离）*/
				H.insert(temp);
			}
	}
	delete[]E;
}

上面的heap数据结构可以用C++ STL里面的priority_queue，也可以自己写一个最小堆，我用的是之前照着书上写的最小堆代码：

最小堆

heap.h 
#pragma once
#include<assert.h>
#include<vector>
using namespace std;
template <typename E, typename Comp>
class heap
{
private:
	E* Heap;		//Pointer to the heap array
	int maxsize;	//Maximum size of the heap
	int n;			//Number of elements now in the heap
		//Helper function to put element in its correct place,and that moves the father node down
	void siftdown(int pos);
public:
	heap(E* h, int num, int max);
	int size()const;
	bool isLeaf(int pos)const;
	int leftchild(int pos)const;
	int rightchild(int pos)const;
	int parent(int pos)const;
	void buildHeap();
	void insert(const E& it);
	E removefirst();
	E remove(int pos);
};


//Swap two elements in the container
template<typename E>
void swap(E* array, int pos1, int pos2) {
	E temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;
}

//Heap class
// E is the element in heap
//Comp is a class used to compare two elements
//Helper function to put element in its correct place,and that moves the father node down
template <typename E, typename Comp>
void heap<E, Comp>::siftdown(int pos) {
	while (!isLeaf(pos)) {//Stop if pos is a leaf
		int j = leftchild(pos);
		int rc = rightchild(pos);
		if ((rc < n) && Comp::prior(Heap[rc], Heap[j]))
			j = rc;		//Set j to greater child's value
		if (Comp::prior(Heap[pos], Heap[j]))
			return;	//Done
		swap(Heap, pos, j);
		pos = j;		//Move down
	}
}

/*
template<typename E, typename Comp>
E& heap<E, Comp>::operator[](int i) {
	assert(i < maxsize);	//Interrupt if i>=maxsize
	return E[i];
}
*/
template <typename E, typename Comp>
heap<E, Comp>::heap(E* h, int num, int max) {
	Heap = h;
	n = num;
	maxsize = max;
	buildHeap();
}
//Return current heap size
template <typename E, typename Comp>
int heap<E, Comp>::size()const {
	return n;
}
//True if pos is a leaf
template <typename E, typename Comp>
bool heap<E, Comp>::isLeaf(int pos)const {
	return ((pos >= n / 2) && (pos < n));
}
//Return leftchild position
template <typename E, typename Comp>
int heap<E, Comp>::leftchild(int pos)const {
	return 2 * pos + 1;
}
//Return rightchild position
template <typename E, typename Comp>
int heap<E, Comp>::rightchild(int pos)const {
	return 2 * pos + 2;
}
//Return parent position
template <typename E, typename Comp>
int heap<E, Comp>::parent(int pos)const {
	return (pos - 1) / 2;
}
//Heapify contents of Heap
template <typename E, typename Comp>
void heap<E, Comp>::buildHeap() {
	for (int i = n / 2 - 1; i >= 0; --i) {
		siftdown(i);
	}
}
//Insert "it" into the heap
template <typename E, typename Comp>
void heap<E, Comp>::insert(const E& it) {
	assert(n < maxsize);	//Terminate if heap is full
	int curr = n++;
	Heap[curr] = it;		//Start at end of heap
	//Move up until curr's parent > curr
	while ((curr != 0) && (Comp::prior(Heap[curr], Heap[parent(curr)]))) {
		swap(Heap, curr, parent(curr));
		curr = parent(curr);
	}
}

template <typename E, typename Comp>
E heap<E, Comp>::removefirst() {
	assert(n > 0);		//Interrupt if heap is empty
	swap(Heap, 0, --n);		//Swap first with last value.
	if (n != 0)siftdown(0);		//Siftdown new root val
	return Heap[n];			//Return deleted value
}

template <typename E, typename Comp>
E heap<E, Comp>::remove(int pos) {
	assert((pos >= 0) && (pos < n));  //Intertupt if it is in bad position
	if (pos == n - 1)n--;		//Last element,no work to do
	else {
		swap(Heap, pos, --n);		//Swap with last value
		while ((pos != 0) && (Comp::prior(Heap[pos], Heap[parent(pos)]))) {
			swap(Heap, pos, parent(pos));		//Push up large key
			pos = parent(pos);
		}
		if (n != 0)siftdown(pos);		//Push down small key
	}
	return Heap[n];
}
堆 图 最短路径
上一篇: POJ 1860 - Currency Exchange（SPFA判正环）
下一篇: 最短路径---Dijkstra算法（单源+边权非负数）

继续阅读