最短路径问题-Dijkstra

概述

与前面说的Floyd算法相比，Dijkstra算法只能求得图中特定顶点到其余所有顶点的最短路径长度，即单源最短路径问题。

算法思路

1、初始化，集合K中加入顶点v，顶点v到其自身的最短距离为0，到其它所有顶点为无穷。

2、遍历与集合K中结点直接相邻的边（U,V,C），其中U属于集合K，V不属于集合K，计算由结点v出发，按照已经得到的最短路径到达U，再由U经过该边达到V时的路径长度。比较所有与集合K中结点直接相邻的非集合K结点该路径长度，其中路径长度最小的顶点被确定为下一个最短路径确定的结点，其最短路径长度即为该路径长度，最后将该结点并入集合K。

3、若集合K中已经包含了所有的点，算法结束，否则重复步骤2。

 给出Dijkstra算法的代码

#include"stdafx.h" #include <iostream>using namespace std; const int MAXSIZE = 10; const int INF = 99999;//当作最大值 typedef struct VertexNode{int Index;//点的编号默认为从1开始char info; };typedef struct MGraph{int edges[MAXSIZE][MAXSIZE];VertexNode nodes[MAXSIZE];int n, e; }; //构建一个用邻接矩阵存储的图 void CreateMGraph(MGraph& g,int n,int e); //迪杰斯特拉算法求图的最短路径 void DijkStra(MGraph& g, int v, int dist[], int path[]); //输出该最短路径 void PrintRoad(int path[],int v);void main(void) {MGraph g;int dist[MAXSIZE];int path[MAXSIZE];CreateMGraph(g, 7, 12);DijkStra(g, 1, dist, path);PrintRoad(path, 7); }void CreateMGraph(MGraph& g, int n,int e) {g.n = n;g.e = e;int vertex1, vertex2;int value;for (int i = 1; i <= n; ++i){g.nodes[i].Index = i;}for (int i = 1; i <= g.n; ++i)for (int j = 1; j <= g.n; ++j){g.edges[i][j] = INF;}for (int j = 1; j <= e; j++){cout << "请输入边的两个点，中间以空格隔开\n";cin >> vertex1 >> vertex2;cout << "请输入该边的权值\n";cin >> value;g.edges[vertex1][vertex2] = value;} }void DijkStra(MGraph& g, int v,int dist[], int path[]) {int i, j, min, u;int visited[MAXSIZE];for (i = 1; i <= g.n; ++i){if (g.edges[v][i] < INF){dist[i] = g.edges[v][i];path[i] = v;}else{dist[i] = -1;path[i] = -1;}visited[i] = 0;}visited[v] = 1;for (i = 1; i <= g.n; ++i){min = INF;for (j = 1; j <= g.n;++j)if (visited[j] == 0 && dist[j] < min){min = dist[j];u = j;}visited[u] = 1;for (j = 1; j <= g.n; ++j){if (visited[j] == 0 && dist[j] > g.edges[u][j] + dist[u]){dist[j] = g.edges[u][j] + dist[u];path[j] = u;}}} }void PrintRoad(int path[],int v) {int stack[MAXSIZE], top = -1;while (path[v]!= -1){stack[++top] = v;v = path[v];}stack[++top] = v;while (top != -1){cout << stack[top--] << " ";}cout << endl; } View Code

总结

以上是生活随笔为你收集整理的最短路径问题-Dijkstra的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。