最短路径查找-迪杰斯特拉算法_c# dijkstra's algorithm

目录

1.迪杰斯特拉算法简介

 2.以下，分别使用C#和PHP实现迪杰斯特拉算法示例代码：

2.1 使用 C# 实现迪杰斯特拉算法（Dijkstra's algorithm）的示例代码

2.2 使用 PHP 实现地杰斯特拉算法（Dijkstra's algorithm）的示例代码

---

1.迪杰斯特拉算法简介

迪杰斯特拉算法（Dijkstra's algorithm）是一种用于解决带权有向图（weighted directed graph）中单源最短路径问题的算法。它以一个节点作为起点，计算该节点到其它所有节点的最短路径。

迪杰斯特拉算法的基本思想是从起点开始，逐步扩展出新的节点，并尝试通过这些节点更新已经扩展过的节点到起点的距离。在每次扩展时，选择当前距离起点最近的未扩展节点进行扩展，并使用该节点到起点的距离更新已经扩展过的节点到起点的距离。重复执行这个过程，直到所有节点都被扩展过为止。

为了实现这个算法，需要使用一个数组来记录每个节点到起点的距离，一个数组来记录每个节点是否已经被扩展过，以及一个二维数组来记录图中每条边的权值。算法的时间复杂度为 O(V^2)，其中 V 表示节点数目。

迪杰斯特拉算法可以通过优先队列（priority queue）来优化，使得时间复杂度降为 O(E log V)，其中 E 表示边数目。优先队列中保存的是与起点距离最小的节点，每次扩展时选取优先队列中距离最小的节点进行扩展。这个算法被称为优先级队列实现的迪杰斯特拉算法（Dijkstra's algorithm with priority queue implementation）。

总之，迪杰斯特拉算法是一种高效、常用的解决单源最短路径问题的算法，在网络路由、地图导航等领域得到广泛应用。

 2.以下，分别使用C#和PHP实现迪杰斯特拉算法示例代码：

2.1 使用 C# 实现迪杰斯特拉算法（Dijkstra's algorithm）的示例代码

以下是一个使用 C# 实现迪杰斯特拉算法（Dijkstra's algorithm）的示例代码。在这个示例中，我们使用一个二维数组 graph 来表示有向带权图，其中 graph[i][j] 表示从节点 i 到节点 j 的边的权值；使用一个一维数组 dist 来记录每个节点到起点的最短路径长度；使用一个布尔型数组 visited 来记录每个节点是否已经被访问过。

using System;

class DijkstraAlgorithmDemo
{
    static void Main(string[] args)
    {
        int[][] graph = new int[][]
        {
            new int[] {0, 10, 3, int.MaxValue},
            new int[] {int.MaxValue, 0, 1, 2},
            new int[] {int.MaxValue, 4, 0, 8},
            new int[] {int.MaxValue, int.MaxValue, int.MaxValue, 0}
        };

        int startNode = 0;
        int[] dist = new int[graph.Length];
        bool[] visited = new bool[graph.Length];

        for (int i = 0; i < graph.Length; i++)
        {
            dist[i] = int.MaxValue;
            visited[i] = false;
        }

        dist[startNode] = 0;

        for (int count = 0; count < graph.Length - 1; count++)
        {
            int u = MinDistance(dist, visited);

            visited[u] = true;

            for (int v = 0; v < graph.Length; v++)
            {
                if (!visited[v] && graph[u][v] != int.MaxValue && dist[u] != int.MaxValue && dist[u] + graph[u][v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        Console.WriteLine("节点到起点的最短路径：");

        for (int i = 0; i < graph.Length; i++)
        {
            if (dist[i] == int.MaxValue)
            {
                Console.WriteLine($"{i} -> 起点: 不可达");
            }
            else
            {
                Console.WriteLine($"{i} -> 起点: {dist[i]}");
            }
        }
    }

    static int MinDistance(int[] dist, bool[] visited)
    {
        int minDist = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < dist.Length; v++)
        {
            if (!visited[v] && dist[v] <= minDist)
            {
                minDist = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }
}
 

在这个示例代码中，我们首先定义了一个二维数组 graph，表示一个有向带权图。然后，定义了一个一维数组 dist 和一个布尔型数组 visited，用于记录每个节点到起点的最短路径长度和节点是否已经被访问过。接着，我们初始化了 dist 数组和 visited 数组，并将起点的距离设为 0。

接下来，我们使用一个循环来依次扩展每个节点，并更新它们到起点的距离。在每次扩展时，我们选取当前距离起点最近的未扩展节点进行扩展，并使用该节点到起点的距离更新已经扩展过的节点到起点的距离。当所有节点都被扩展过后，dist 数组中记录的就是每个节点到起点的最短路径长度。

最后，我们将每个节点到起点的最短路径长度输出到控制台上。

2.2 使用 PHP 实现地杰斯特拉算法（Dijkstra's algorithm）的示例代码

以下是一个使用 PHP 实现地杰斯特拉算法（Dijkstra's algorithm）的示例代码。在这个示例中，我们使用一个二维数组 $graph 来表示有向带权图，其中 $graph[$i][$j] 表示从节点 i 到节点 j 的边的权值；使用一个一维数组 $dist 来记录每个节点到起点的最短路径长度；使用一个布尔型数组 $visited 来记录每个节点是否已经被访问过。

<?php

$graph = array(
    array(0, 10, 3, INF),
    array(INF, 0, 1, 2),
    array(INF, 4, 0, 8),
    array(INF, INF, INF, 0)
);

$startNode = 0;
$dist = array();
$visited = array();

for ($i = 0; $i < count($graph); $i++) {
    $dist[$i] = INF;
    $visited[$i] = false;
}

$dist[$startNode] = 0;

for ($count = 0; $count < count($graph) - 1; $count++) {
    $u = minDistance($dist, $visited);

    $visited[$u] = true;

    for ($v = 0; $v < count($graph); $v++) {
        if (!$visited[$v] && $graph[$u][$v] != INF && $dist[$u] != INF && $dist[$u] + $graph[$u][$v] < $dist[$v]) {
            $dist[$v] = $dist[$u] + $graph[$u][$v];
        }
    }
}

echo "节点到起点的最短路径：\n";

for ($i = 0; $i < count($graph); $i++) {
    if ($dist[$i] == INF) {
        echo "$i -> 起点: 不可达\n";
    } else {
        echo "$i -> 起点: {$dist[$i]}\n";
    }
}

function minDistance($dist, $visited) {
    $minDist = INF;
    $minIndex = -1;

    for ($v = 0; $v < count($dist); $v++) {
        if (!$visited[$v] && $dist[$v] <= $minDist) {
            $minDist = $dist[$v];
            $minIndex = $v;
        }
    }

    return $minIndex;
}

?>
 

在这个示例代码中，我们首先定义了一个二维数组 $graph，表示一个有向带权图。然后，定义了一个一维数组 $dist 和一个布尔型数组 $visited，用于记录每个节点到起点的最短路径长度和节点是否已经被访问过。接着，我们初始化了 $dist 数组和 $visited 数组，并将起点的距离设为 0。

接下来，我们使用一个循环来依次扩展每个节点，并更新它们到起点的距离。在每次扩展时，我们选取当前距离起点最近的未扩展节点进行扩展，并使用该节点到起点的距离更新已经扩展过的节点到起点的距离。当所有节点都被扩展过后，$dist 数组中记录的就是每个节点到起点的最短路径长度。

最后，我们将每个节点到起点的最短路径长度输出到控制台上。