C++ 最短路Dijkstra

Dijkstra朴素算法特点：

非负边权

单源最短路

顶点数最好少于1000

少量数据结构知识和一点点的算法基础

算法描述：

第一步建图，任何算法都需要考虑，用啥结构来存储，这个算法我们采取领接矩阵来存储，有时候输入数据，所以需要对数据做一些处理，也就是把图建立起来的过程。

第二步辅助数组，对于图G=[V, E]，源点为s，dist[i] 表示s到i的最短路径，visited[i]表示dist[i]是否确定（布尔值），即s到i的最短路径，是否已确定。

第三步初始化，所有节点的数据见下

dist[i] = ∞ （0 <= i < n）

visited[i] = false （0 <= i < n）

dist[s] = 0

第四步找距离最小的点，从所有的visited[i]为false的顶点中找到一个dist[i]值最小的，令x=i，并且标记visited[x]为true，如果找不到，算法结束

第五步更新其余点的距离，更新从x出发的，到达顶点y的最小距离为dist[y]，dist[y] = min(dist[y], dist[x]+w(x,y))

第六步重复执行，回到第四步，继续计算距离最小值

代码分析：

第一步，初始化邻接矩阵

function initEdges(graph, n)

  for u -> (0, n-1)

    for v -> (0, n-1)

      graph[u][v] = inf

第二步，边的添加

function addEdge(graph, u, v, w)

  graph[u][v] = min(graph[u][v], w)

第三步，建图，根据题目给出的数据，调用addEdge

addEdge(graph, u1, v1, w1)

addEdge(graph, u2, v2, w2)

...

第四步，框架代码

function Dijkstra(graph, n, s, dist)

  visited[]

  DijsktraInit(n, s, visited, dist)

  while true

    u = DilsktraFindMin(n, visited, dist)

    if u == -1 return

    DijsktraUpdate(graph, n, u, visited, dist)

第五步，Dijsktra初始化

function DijsktraInit(n, s, visited, dist)

  for i -> (0, n-1)

    visited[i] = false

    dist[i] = inf

  dist[s] = 0

第六步 Dijsktra找最小距离

function DijsktraFindMin(n, visited, dist)

  u = -1

  for i-> (0, n-1)

    if visited[i] continue

    if u == -1 or dist[i] < dist[u]

      u = i

return u

第七步，Dijsktra更新

function DilsktraUpdate(graph, n, u, visited, dist)

  visited[u] = true

  for i -> (0, n-1)

    if visited[i] continue

     dist[i] = min(dist[i], dist[u] + graph[u][i])

代码练习 1 对应力扣 网络延迟时间，代码见下

#define maxn 101
#define edgeType int
#define inf INT_MAX
class Solution {edgeType graph[maxn][maxn];void initEdge(int n){for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){graph[i][j] = inf;}}}void addEdge(int u, int v, edgeType w){if(graph[u][v] == inf || w < graph[u][v]){graph[u][v] = w;}}void dijkstra(int n, int s, edgeType dist[maxn]){bool visited[maxn];for(int i=0; i<n; ++i){visited[i] = false;dist[i] = inf;}dist[s] = 0;while(1){edgeType minDist = inf;int minIndex;for(int i=0; i<n; ++i){if(visited[i]){continue;}if(minDist == inf || dist[i] < minDist){minDist = dist[i];minIndex = i;}}if(minDist == inf){break;}visited[minIndex] = true;for(int i=0; i<n; ++i){if(visited[i]){continue;}int dis = graph[minIndex][i];if(dis == inf){continue;}if(dist[i] == inf || dist[minIndex] + dis < dist[i]){dist[i] = dist[minIndex] + dis;}}}}
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {initEdge(n);for(int i=0; i<times.size(); ++i){int u = times[i][0] - 1;int v = times[i][1] - 1;edgeType w = times[i][2];addEdge(u, v, w);}edgeType dist[maxn];dijkstra(n, k-1, dist);int max = 0;for(int i=0; i<n; ++i){if(dist[i] == inf){return -1;}if(dist[i] > max){max = dist[i];}}return max;}
};

代码练习2 阈值距离内邻居最少的城市，代码见下

#define maxn 101
#define edgeType int
#define inf INT_MAX
class Solution {edgeType graph[maxn][maxn];void initEdge(int n){for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){graph[i][j] = inf;}}}void addEdge(int u, int v, edgeType w){if(graph[u][v] == inf || w < graph[u][v]){graph[u][v] = w;}}void dijkstra(int n, int s, edgeType dist[maxn]){bool visited[maxn];for(int i=0; i<n; ++i){visited[i] = false;dist[i] = inf;}dist[s] = 0;while(1){edgeType minDist = inf;int minIndex;for(int i=0; i<n; ++i){if(visited[i]){continue;}if(minDist == inf || dist[i] < minDist){minDist = dist[i];minIndex = i;}}if(minDist == inf){break;}visited[minIndex] = true;for(int i=0; i<n; ++i){if(visited[i]){continue;}int dis = graph[minIndex][i];if(dis == inf){continue;}if(dist[i] == inf || dist[minIndex] + dis < dist[i]){dist[i] = dist[minIndex] + dis;}}}}
public:int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {initEdge(n);for(int i=0; i<edges.size(); ++i){int u = edges[i][0];int v = edges[i][1];edgeType w = edges[i][2];addEdge(u, v, w);addEdge(v, u, w);}int retCnt = 100000000;int retIdx = -1;for(int i = n-1; i >= 0; --i){edgeType dist[maxn];dijkstra(n, i, dist);int cnt = 0;for(int j=0; j<n; ++j){if(dist[j] <= distanceThreshold){++cnt;}}if(cnt < retCnt){retCnt = cnt;retIdx = i;}}return retIdx;}
};

代码练习三，对应力扣，前往目标的最小代价，代码见下

long long point[402];
int pointSize;#define base 100001
int findPoint(int x, int y){long long p = (long long)x * base + y;for(int i=0; i<pointSize; ++i){if(p == point[i]){return i;}}point[pointSize++] = p;return pointSize - 1;
}
#define maxn 402
#define edgeType int
#define inf INT_MAXclass Solution {
edgeType graph[maxn][maxn];void initEdge(int n){for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){graph[i][j] = inf;}}}void addEdge(int u, int v, edgeType w){if(graph[u][v] == inf || w < graph[u][v]){graph[u][v] = w;}}void dijkstra(int n, int s, edgeType dist[maxn]){bool visited[maxn];for(int i=0; i<n; ++i){visited[i] = false;dist[i] = inf;}dist[s] = 0;while(1){edgeType minDist = inf;int minIndex;for(int i=0; i<n; ++i){if(visited[i]){continue;}if(minDist == inf || dist[i] < minDist){minDist = dist[i];minIndex = i;}}if(minDist == inf){break;}visited[minIndex] = true;for(int i=0; i<n; ++i){if(visited[i]){continue;}int dis = graph[minIndex][i];if(dis == inf){continue;}if(dist[i] == inf || dist[minIndex] + dis < dist[i]){dist[i] = dist[minIndex] + dis;}}}}public:int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {pointSize = 0;initEdge(maxn);int s = findPoint(start[0], start[1]);int t = findPoint(target[0], target[1]);for(int i=0; i<specialRoads.size(); ++i){int u = findPoint(specialRoads[i][0], specialRoads[i][1]);int v = findPoint(specialRoads[i][2], specialRoads[i][3]);edgeType w = specialRoads[i][4];addEdge(u, v, w);}for(int i = 0; i<pointSize; ++i){int x1 = point[i] / base;int y1 = point[i] % base;for(int j = 0; j<pointSize; ++j){int x2 = point[j] / base;int y2 = point[j] % base;int w = abs(x1 - x2) + abs(y1 - y2);addEdge(i,j, w);}}edgeType dist[maxn];dijkstra(pointSize, s, dist);return dist[t];}
};