Module: Dijkstra 算法


Problem

1/14

Dijkstra：开端 (C++)

Theory Click to read/hide

<分区>

给定一个具有 n 个顶点和 m 条边的有向或无向加权图。所有边的权重都是非负的。指定了一些起始顶点。您需要找到从顶点 s 到所有其他顶点的最短路径的长度，并提供一种打印最短路径本身的方法。
 
这个问题叫做“单源最短路径问题” （单源最短路径问题）。

执行与 1-K BFS 相同的任务，但不考虑 K。此外，与 1-K BFS 一样，它不能正确处理负边缘

算法：
Dijkstra 算法本身由 N 次迭代组成。在下一次迭代中，顶点 V 从尚未标记的顶点到它的最小距离，这个顶点被标记并且相邻顶点的松弛从它发生。


 算法的最终渐近行为是：O(n2+ m)

Problem

给你一个有向加权图。找出从一个给定顶点到另一个顶点的最短距离。
 
输入
第一行包含三个数字：N、S和F（1≤N≤100、1≤S、F≤N），其中N–图的顶点数，S –初始顶点和 F –最终的。在接下来的 N 行中，每行输入 N 个数字，不超过 100，–图的权重邻接矩阵，其中-1表示顶点之间没有边，任意非负数–给定权重的边缘的存在。零写在矩阵的主对角线上。
 
输出
要求显示所需的距离，如果指定顶点之间没有路径，则显示-1。

例子 <头> <日># <正文>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
1
3 2 1
0 1 1
4 0 1
2 1 0
 3
Write the program below 
#include<iostream>
 
using namespace std;
 
int main()
{
    const int N1 = 110;
    int N, S, F, g[N1][N1], i, j, mini, d[N1];
    bool used[N1];
   
    cin >> N >> S >> F;
   
    fill(used, used + N, false);
   
    fill(d, d + N, 10000000);
   
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            cin >> g[i][j];
    }
   
    d[S - 1] = 0;
   
    for (i = 0; i < N; i++)
    {
        mini = -1;
       
        for (j = 0; j < N; j++)
        {
            if (!used[j] && (mini == -1 || d[j] < d[mini]))
                mini = j;
        }
       
        used[mini] = true; 
    if (d[F - 1] == 10000000)
        cout << "-1";
    else
        cout << d[F - 1];
}

     

Program check result

To check the solution of the problem, you need to register or log in!