Dijkstra最短路径算法

给定一个图和图中的一个源顶点A，找到从源顶点A到给定图中所有顶点的最短路径，边的数值为顶点之间的距离。

Dijkstra算法与Prim算法的MST（最小生成树）一样，生成以给定源为根的SPT（最短路径树）。维护两组集合，一组包含包含在SPT中的顶点，另一组包含尚未包含在SPT中的顶点。在算法的每一步，找到尚未包含在SPT集合中其与源顶点距离最小的顶点，并加入到SPT中。

步骤：

1. 创建SPT空集合和一个包含N的顶点的dist距离数组，源顶点的距离初始化为0，其它顶点为无限大。
2. 从dist数组选择一个距离最小并且不在SPT集合中的顶点v。
3. 把顶点v加入SPT集合。
4. 更新与顶点v相邻顶点的dist距离值，重复2~4步，直到SPT包含所有的顶点。
5. dist数组即为从源顶点到所有顶点的最短距离。

算法结果演示

sptSet: A
dist: [0, inf, inf, inf, inf, inf, inf, inf, inf]
----------------------------------------
sptSet: A C
dist: [0, 3, 2, inf, inf, inf, inf, inf, inf]
----------------------------------------
sptSet: A C B
dist: [0, 3, 2, 9, 8, inf, inf, 10, inf]
----------------------------------------
sptSet: A C B F
dist: [0, 3, 2, 8, 8, 7, inf, 10, inf]
----------------------------------------
sptSet: A C B F D
dist: [0, 3, 2, 8, 8, 7, 12, 10, 12]
----------------------------------------
sptSet: A C B F D E
dist: [0, 3, 2, 8, 8, 7, 12, 10, 12]
----------------------------------------
sptSet: A C B F D E H
dist: [0, 3, 2, 8, 8, 7, 12, 10, 12]
----------------------------------------
sptSet: A C B F D E H G
dist: [0, 3, 2, 8, 8, 7, 12, 10, 12]
----------------------------------------
sptSet: A C B F D E H G I
dist: [0, 3, 2, 8, 8, 7, 12, 10, 12]
----------------------------------------

代码实现（python， C）

# python

import sys

class Graph():
    def __init__(self, vertices):
        self.vertices = vertices
        self.graph = [[0 for column in range(vertices)]
                    for row in range(vertices)]

    def show(self, dist):
        print("Vertex \t\tDistance from Source")
        for v in range(self.vertices):
            print(chr(v+65), "\t\t", dist[v])

    def minDistance(self, dist, sptSet):
        min = sys.maxsize

        for v in range(self.vertices):
            if dist[v] < min and v not in sptSet:
                min = dist[v]
                min_index = v

        return min_index

    def dijkstra(self, src):
        dist = [sys.maxsize] * self.vertices  # 记录从原点出发，到每个节点的距离，初始为无限远
        dist[src] = 0
        sptSet = []

        for cout in range(self.vertices):
            x = self.minDistance(dist, sptSet)

            sptSet.append(x)

            for y in range(self.vertices):
                # 与x顶点相邻且不在setSet中,x到相邻顶点的距离小于目前dist记录的距离，
                # 则更新相应顶点在dist中距离
                if self.graph[x][y] > 0 and y not in sptSet and \
                    dist[y] > dist[x] + self.graph[x][y]:
                    dist[y] = dist[x] + self.graph[x][y]

        self.show(dist)

g = Graph(9)

# graph表示每个顶点和其它顶点的距离，0表示没有相连
          # 0,  1,  2, 3,  4,  5,  6, 7,  8
g.graph = [[0,  3,  2, 0,  0,  0,  0, 0, 0],  #0
           [3,  0,  0, 5,  0,  4,  0, 0, 0],  #1
           [2,  0,  0, 7,  6,  0,  0, 8, 0], #2
           [0,  5,  7, 0,  4,  0,  0, 0, 0], #3
           [0,  0,  6, 4,  0,  8,  0, 0, 9], #4
           [0,  4,  0, 0,  8,  0,  5, 0, 5], #5
           [0,  0,  0, 0,  0,  5,  0, 0, 3], #6
           [0,  0,  8, 0,  0,  0,  0, 0, 4], #7
           [0,  0,  0, 0,  9,  5,  3, 4, 0]];#8


g.dijkstra(0);

// C

#include <string.h>
#include <stdio.h>
#include <stdint.h>

#define VERTICES 9

void show(uint32_t dist[])
{
    printf("Vertex \t\tDistance from Source\n");

    for(int v = 0; v < VERTICES; v++)
        printf("%c\t\t%u\n", 'A' + v, dist[v]);
}


uint32_t minDistance(uint32_t dist[], uint32_t sptSet[])
{
    uint32_t min = ~(0);
    uint32_t min_index = 0;

    for(int v = 0; v < VERTICES; v++) {
        if (dist[v] < min && sptSet[v] == 0) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}

void dijkstra(uint32_t graph[][VERTICES], int src_vertice)
{
    uint32_t dist[VERTICES] = {~0};  // 记录从原点出发，到每个节点的距离，初始为无限远
    uint32_t sptSet[VERTICES] = {0};

    memset(dist, ~0, sizeof(dist));
    memset(sptSet, 0, sizeof(sptSet));

    dist[src_vertice] = 0;

    for (int i = 0; i < VERTICES; i++) {
        int x = minDistance(dist, sptSet);

        sptSet[x] = 1;

        for (int y = 0; y < VERTICES; y++) {
            /* 与x顶点相邻且不在setSet中,x到相邻顶点的距离小于目前dist记录的距离，
               则更新相应顶点在dist中距离*/
            if (graph[x][y] > 0 && sptSet[y] == 0 &&
                dist[y] > dist[x] + graph[x][y]) {
                dist[y] = dist[x] + graph[x][y];
            }
        }
    }

    show(dist);
}

void main(void)
{
    // graph表示每个顶点和其它顶点的距离，0表示没有相连
    uint32_t graph[][VERTICES] =
     // 0,  1,  2, 3,  4,  5,  6, 7,  8
      {{0,  3,  2, 0,  0,  0,  0, 0, 0},  // 0
       {3,  0,  0, 5,  0,  4,  0, 0, 0},  // 1
       {2,  0,  0, 7,  6,  0,  0, 8, 0},  // 2
       {0,  5,  7, 0,  4,  0,  0, 0, 0},  // 3
       {0,  0,  6, 4,  0,  8,  0, 0, 9},  // 4
       {0,  4,  0, 0,  8,  0,  5, 0, 5},  // 5
       {0,  0,  0, 0,  0,  5,  0, 0, 3},  // 6
       {0,  0,  8, 0,  0,  0,  0, 0, 4},  // 7
       {0,  0,  0, 0,  9,  5,  3, 4, 0}}; // 8

    dijkstra(graph, 0);
}